﻿<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3c.org/TR/1999/REC-html401-19991224/loose.dtd">
<!-- saved from url=(0051)http://en.wikipedia.org/wiki/Algorithmics_of_sudoku -->
<HTML lang=en dir=ltr xml:lang="en" 
xmlns="http://www.w3.org/1999/xhtml"><HEAD><TITLE>Algorithmics of sudoku - Wikipedia, the free encyclopedia</TITLE>
<META http-equiv=Content-Type content="text/html; charset=utf-8">
<META http-equiv=Content-Style-Type content=text/css>
<META content="MSHTML 6.00.2900.5880" name=GENERATOR><LINK 
title="Edit this page" 
href="/w/index.php?title=Algorithmics_of_sudoku&amp;action=edit" 
type=application/x-wiki rel=alternate><LINK title="Edit this page" 
href="/w/index.php?title=Algorithmics_of_sudoku&amp;action=edit" rel=edit><LINK 
href="http://en.wikipedia.org/apple-touch-icon.png" rel=apple-touch-icon><LINK 
href="/favicon.ico" rel="shortcut icon"><LINK title="Wikipedia (en)" 
href="/w/opensearch_desc.php" type=application/opensearchdescription+xml 
rel=search><LINK href="http://creativecommons.org/licenses/by-sa/3.0/" 
rel=copyright><LINK title="Wikipedia RSS Feed" 
href="/w/index.php?title=Special:RecentChanges&amp;feed=rss" 
type=application/rss+xml rel=alternate><LINK title="Wikipedia Atom Feed" 
href="/w/index.php?title=Special:RecentChanges&amp;feed=atom" 
type=application/atom+xml rel=alternate><LINK media=screen 
href="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/shared.css" 
type=text/css rel=stylesheet><LINK media=print 
href="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/commonPrint.css" 
type=text/css rel=stylesheet><LINK media=screen 
href="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/main.css" 
type=text/css rel=stylesheet><LINK media=handheld 
href="G:\l论文资料\sudoku开发参考资料\遗传算法\Algorithmics of sudoku - Wikipedia, the free encyclopedia.files\main(1).css" 
type=text/css rel=stylesheet><!--[if lt IE 5.5000]><link rel="stylesheet" href="/skins-1.5/monobook/IE50Fixes.css?243z2" type="text/css" media="screen" /><![endif]--><!--[if IE 5.5000]><link rel="stylesheet" href="/skins-1.5/monobook/IE55Fixes.css?243z2" type="text/css" media="screen" /><![endif]--><!--[if IE 6]><LINK 
media=screen 
href="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/IE60Fixes.css" 
type=text/css rel=stylesheet><![endif]--><!--[if IE 7]><link rel="stylesheet" href="/skins-1.5/monobook/IE70Fixes.css?243z2" type="text/css" media="screen" /><![endif]--><LINK 
media=all 
href="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/index.css" 
type=text/css rel=stylesheet><LINK media=print 
href="G:\l论文资料\sudoku开发参考资料\遗传算法\Algorithmics of sudoku - Wikipedia, the free encyclopedia.files\index(1).css" 
type=text/css rel=stylesheet><LINK media=handheld 
href="G:\l论文资料\sudoku开发参考资料\遗传算法\Algorithmics of sudoku - Wikipedia, the free encyclopedia.files\index(2).css" 
type=text/css rel=stylesheet><LINK media=all 
href="G:\l论文资料\sudoku开发参考资料\遗传算法\Algorithmics of sudoku - Wikipedia, the free encyclopedia.files\index(3).css" 
type=text/css rel=stylesheet><LINK media=all 
href="G:\l论文资料\sudoku开发参考资料\遗传算法\Algorithmics of sudoku - Wikipedia, the free encyclopedia.files\index(4).css" 
type=text/css rel=stylesheet>
<SCRIPT type=text/javascript>
var skin="monobook",
stylepath="/skins-1.5",
wgArticlePath="/wiki/$1",
wgScriptPath="/w",
wgScriptExtension=".php",
wgScript="/w/index.php",
wgVariantArticlePath=false,
wgActionPaths={},
wgServer="http://en.wikipedia.org",
wgCanonicalNamespace="",
wgCanonicalSpecialPageName=false,
wgNamespaceNumber=0,
wgPageName="Algorithmics_of_sudoku",
wgTitle="Algorithmics of sudoku",
wgAction="view",
wgArticleId=8444301,
wgIsArticle=true,
wgUserName=null,
wgUserGroups=null,
wgUserLanguage="en",
wgContentLanguage="en",
wgBreakFrames=false,
wgCurRevisionId=322090206,
wgVersion="1.16alpha-wmf",
wgEnableAPI=true,
wgEnableWriteAPI=true,
wgSeparatorTransformTable=["", ""],
wgDigitTransformTable=["", ""],
wgMainPageTitle="Main Page",
wgFormattedNamespaces={"-2": "Media", "-1": "Special", "0": "", "1": "Talk", "2": "User", "3": "User talk", "4": "Wikipedia", "5": "Wikipedia talk", "6": "File", "7": "File talk", "8": "MediaWiki", "9": "MediaWiki talk", "10": "Template", "11": "Template talk", "12": "Help", "13": "Help talk", "14": "Category", "15": "Category talk", "100": "Portal", "101": "Portal talk"},
wgNamespaceIds={"media": -2, "special": -1, "": 0, "talk": 1, "user": 2, "user_talk": 3, "wikipedia": 4, "wikipedia_talk": 5, "file": 6, "file_talk": 7, "mediawiki": 8, "mediawiki_talk": 9, "template": 10, "template_talk": 11, "help": 12, "help_talk": 13, "category": 14, "category_talk": 15, "portal": 100, "portal_talk": 101, "wp": 4, "wt": 5, "image": 6, "image_talk": 7},
wgMWSuggestTemplate="http://en.wikipedia.org/w/api.php?action=opensearch\x26search={searchTerms}\x26namespace={namespaces}\x26suggest",
wgDBname="enwiki",
wgSearchNamespaces=[0],
wgMWSuggestMessages=["with suggestions", "no suggestions"],
wgRestrictionEdit=[],
wgRestrictionMove=[],
wgNotice="",
wgNoticeLocal="";
</SCRIPT>

<SCRIPT 
src="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/wikibits.js" 
type=text/javascript></SCRIPT>

<SCRIPT 
src="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/ajax.js" 
type=text/javascript></SCRIPT>

<SCRIPT 
src="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/mwsuggest.js" 
type=text/javascript></SCRIPT>

<SCRIPT 
src="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/centralnotice.js" 
type=text/javascript></SCRIPT>
<!--[if lt IE 7]>
<SCRIPT 
src="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/IEFixes.js" 
type=text/javascript></SCRIPT>

<META http-equiv=imagetoolbar content=no><![endif]-->
<SCRIPT 
src="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/index.php" 
type=text/javascript></SCRIPT>

<STYLE type=text/css>.source-java {
	LINE-HEIGHT: normal
}
.source-java LI {
	BORDER-RIGHT: white 0px; BORDER-TOP: white 0px; BORDER-LEFT: white 0px; LINE-HEIGHT: normal; BORDER-BOTTOM: white 0px
}
.source-java PRE {
	BORDER-RIGHT: white 0px; BORDER-TOP: white 0px; BORDER-LEFT: white 0px; LINE-HEIGHT: normal; BORDER-BOTTOM: white 0px
}
.source-java .de1 {
	PADDING-RIGHT: 0px; PADDING-LEFT: 0px; BACKGROUND: none transparent scroll repeat 0% 0%; PADDING-BOTTOM: 0px; MARGIN: 0px; FONT: 1em/1.2em monospace; VERTICAL-ALIGN: top; PADDING-TOP: 0px
}
.source-java .de2 {
	PADDING-RIGHT: 0px; PADDING-LEFT: 0px; BACKGROUND: none transparent scroll repeat 0% 0%; PADDING-BOTTOM: 0px; MARGIN: 0px; FONT: 1em/1.2em monospace; VERTICAL-ALIGN: top; PADDING-TOP: 0px
}
.source-java {
	FONT-FAMILY: monospace
}
.source-java .imp {
	FONT-WEIGHT: bold; COLOR: red
}
.source-java LI {
	FONT-WEIGHT: normal; VERTICAL-ALIGN: top
}
.source-java .li1 {
	FONT-WEIGHT: normal; VERTICAL-ALIGN: top
}
.source-java .ln {
	PADDING-RIGHT: 2px; PADDING-LEFT: 2px; PADDING-BOTTOM: 0px; MARGIN: 0px; VERTICAL-ALIGN: top; WIDTH: 1px; PADDING-TOP: 0px; TEXT-ALIGN: right
}
.source-java .li2 {
	FONT-WEIGHT: bold; VERTICAL-ALIGN: top
}
.source-java .kw1 {
	FONT-WEIGHT: bold; COLOR: #000000
}
.source-java .kw2 {
	FONT-WEIGHT: bold; COLOR: #000066
}
.source-java .kw3 {
	COLOR: #003399
}
.source-java .kw4 {
	FONT-WEIGHT: bold; COLOR: #000066
}
.source-java .co1 {
	COLOR: #666666; FONT-STYLE: italic
}
.source-java .co2 {
	COLOR: #006699
}
.source-java .co3 {
	FONT-WEIGHT: bold; COLOR: #008000; FONT-STYLE: italic
}
.source-java .coMULTI {
	COLOR: #666666; FONT-STYLE: italic
}
.source-java .es0 {
	FONT-WEIGHT: bold; COLOR: #000099
}
.source-java .br0 {
	COLOR: #009900
}
.source-java .sy0 {
	COLOR: #339933
}
.source-java .st0 {
	COLOR: #0000ff
}
.source-java .nu0 {
	COLOR: #cc66cc
}
.source-java .me1 {
	COLOR: #006633
}
.source-java .me2 {
	COLOR: #006633
}
.source-java .ln-xtra {
	BACKGROUND-COLOR: #ffc
}
.source-java LI.ln-xtra {
	BACKGROUND-COLOR: #ffc
}
.source-java DIV.ln-xtra {
	BACKGROUND-COLOR: #ffc
}
.source-java SPAN.xtra {
	DISPLAY: block
}
</STYLE>

<STYLE type=text/css>@import url( /w/index.php?title=MediaWiki:Geshi.css&usemsgcache=yes&action=raw&ctype=text/css&smaxage=2678400 );
</STYLE>

<STYLE type=text/css>.source-ruby {
	LINE-HEIGHT: normal
}
.source-ruby LI {
	BORDER-RIGHT: white 0px; BORDER-TOP: white 0px; BORDER-LEFT: white 0px; LINE-HEIGHT: normal; BORDER-BOTTOM: white 0px
}
.source-ruby PRE {
	BORDER-RIGHT: white 0px; BORDER-TOP: white 0px; BORDER-LEFT: white 0px; LINE-HEIGHT: normal; BORDER-BOTTOM: white 0px
}
.source-ruby .de1 {
	PADDING-RIGHT: 0px; PADDING-LEFT: 0px; BACKGROUND: none transparent scroll repeat 0% 0%; PADDING-BOTTOM: 0px; MARGIN: 0px; FONT: 1em/1.2em monospace; VERTICAL-ALIGN: top; PADDING-TOP: 0px
}
.source-ruby .de2 {
	PADDING-RIGHT: 0px; PADDING-LEFT: 0px; BACKGROUND: none transparent scroll repeat 0% 0%; PADDING-BOTTOM: 0px; MARGIN: 0px; FONT: 1em/1.2em monospace; VERTICAL-ALIGN: top; PADDING-TOP: 0px
}
.source-ruby {
	FONT-FAMILY: monospace
}
.source-ruby .imp {
	FONT-WEIGHT: bold; COLOR: red
}
.source-ruby LI {
	FONT-WEIGHT: normal; VERTICAL-ALIGN: top
}
.source-ruby .li1 {
	FONT-WEIGHT: normal; VERTICAL-ALIGN: top
}
.source-ruby .ln {
	PADDING-RIGHT: 2px; PADDING-LEFT: 2px; PADDING-BOTTOM: 0px; MARGIN: 0px; VERTICAL-ALIGN: top; WIDTH: 1px; PADDING-TOP: 0px; TEXT-ALIGN: right
}
.source-ruby .li2 {
	FONT-WEIGHT: bold; VERTICAL-ALIGN: top
}
.source-ruby .kw1 {
	FONT-WEIGHT: bold; COLOR: #9966cc
}
.source-ruby .kw2 {
	FONT-WEIGHT: bold; COLOR: #0000ff
}
.source-ruby .kw3 {
	FONT-WEIGHT: bold; COLOR: #cc0066
}
.source-ruby .kw4 {
	FONT-WEIGHT: bold; COLOR: #cc00ff
}
.source-ruby .co1 {
	COLOR: #008000; FONT-STYLE: italic
}
.source-ruby .coMULTI {
	COLOR: #000080; FONT-STYLE: italic
}
.source-ruby .es0 {
	COLOR: #000099
}
.source-ruby .br0 {
	FONT-WEIGHT: bold; COLOR: #006600
}
.source-ruby .sy0 {
	FONT-WEIGHT: bold; COLOR: #006600
}
.source-ruby .st0 {
	COLOR: #996600
}
.source-ruby .nu0 {
	COLOR: #006666
}
.source-ruby .me1 {
	COLOR: #9900cc
}
.source-ruby .re0 {
	FONT-WEIGHT: bold; COLOR: #ff6633
}
.source-ruby .re1 {
	FONT-WEIGHT: bold; COLOR: #0066ff
}
.source-ruby .re2 {
	FONT-WEIGHT: bold; COLOR: #6666ff
}
.source-ruby .re3 {
	FONT-WEIGHT: bold; COLOR: #ff3333
}
.source-ruby .ln-xtra {
	BACKGROUND-COLOR: #ffc
}
.source-ruby LI.ln-xtra {
	BACKGROUND-COLOR: #ffc
}
.source-ruby DIV.ln-xtra {
	BACKGROUND-COLOR: #ffc
}
.source-ruby SPAN.xtra {
	DISPLAY: block
}
</STYLE>

<STYLE type=text/css>@import url( /w/index.php?title=MediaWiki:Geshi.css&usemsgcache=yes&action=raw&ctype=text/css&smaxage=2678400 );
</STYLE>

<STYLE type=text/css>.source-c {
	LINE-HEIGHT: normal
}
.source-c LI {
	BORDER-RIGHT: white 0px; BORDER-TOP: white 0px; BORDER-LEFT: white 0px; LINE-HEIGHT: normal; BORDER-BOTTOM: white 0px
}
.source-c PRE {
	BORDER-RIGHT: white 0px; BORDER-TOP: white 0px; BORDER-LEFT: white 0px; LINE-HEIGHT: normal; BORDER-BOTTOM: white 0px
}
.source-c .de1 {
	PADDING-RIGHT: 0px; PADDING-LEFT: 0px; BACKGROUND: none transparent scroll repeat 0% 0%; PADDING-BOTTOM: 0px; MARGIN: 0px; FONT: 1em/1.2em monospace; VERTICAL-ALIGN: top; PADDING-TOP: 0px
}
.source-c .de2 {
	PADDING-RIGHT: 0px; PADDING-LEFT: 0px; BACKGROUND: none transparent scroll repeat 0% 0%; PADDING-BOTTOM: 0px; MARGIN: 0px; FONT: 1em/1.2em monospace; VERTICAL-ALIGN: top; PADDING-TOP: 0px
}
.source-c {
	FONT-FAMILY: monospace
}
.source-c .imp {
	FONT-WEIGHT: bold; COLOR: red
}
.source-c LI {
	FONT-WEIGHT: normal; VERTICAL-ALIGN: top
}
.source-c .li1 {
	FONT-WEIGHT: normal; VERTICAL-ALIGN: top
}
.source-c .ln {
	PADDING-RIGHT: 2px; PADDING-LEFT: 2px; PADDING-BOTTOM: 0px; MARGIN: 0px; VERTICAL-ALIGN: top; WIDTH: 1px; PADDING-TOP: 0px; TEXT-ALIGN: right
}
.source-c .li2 {
	FONT-WEIGHT: bold; VERTICAL-ALIGN: top
}
.source-c .kw1 {
	COLOR: #b1b100
}
.source-c .kw2 {
	FONT-WEIGHT: bold; COLOR: #000000
}
.source-c .kw3 {
	COLOR: #000066
}
.source-c .kw4 {
	COLOR: #993333
}
.source-c .co1 {
	COLOR: #666666; FONT-STYLE: italic
}
.source-c .co2 {
	COLOR: #339933
}
.source-c .coMULTI {
	COLOR: #808080; FONT-STYLE: italic
}
.source-c .es0 {
	FONT-WEIGHT: bold; COLOR: #000099
}
.source-c .es1 {
	FONT-WEIGHT: bold; COLOR: #000099
}
.source-c .es2 {
	FONT-WEIGHT: bold; COLOR: #660099
}
.source-c .es3 {
	FONT-WEIGHT: bold; COLOR: #660099
}
.source-c .es4 {
	FONT-WEIGHT: bold; COLOR: #660099
}
.source-c .es5 {
	FONT-WEIGHT: bold; COLOR: #006699
}
.source-c .br0 {
	COLOR: #009900
}
.source-c .sy0 {
	COLOR: #339933
}
.source-c .st0 {
	COLOR: #ff0000
}
.source-c .nu0 {
	COLOR: #0000dd
}
.source-c .nu6 {
	COLOR: #208080
}
.source-c .nu8 {
	COLOR: #208080
}
.source-c .nu12 {
	COLOR: #208080
}
.source-c .nu16 {
	COLOR: #800080
}
.source-c .nu17 {
	COLOR: #800080
}
.source-c .nu18 {
	COLOR: #800080
}
.source-c .nu19 {
	COLOR: #800080
}
.source-c .me1 {
	COLOR: #202020
}
.source-c .me2 {
	COLOR: #202020
}
.source-c .ln-xtra {
	BACKGROUND-COLOR: #ffc
}
.source-c LI.ln-xtra {
	BACKGROUND-COLOR: #ffc
}
.source-c DIV.ln-xtra {
	BACKGROUND-COLOR: #ffc
}
.source-c SPAN.xtra {
	DISPLAY: block
}
</STYLE>

<STYLE type=text/css>@import url( /w/index.php?title=MediaWiki:Geshi.css&usemsgcache=yes&action=raw&ctype=text/css&smaxage=2678400 );
</STYLE>
</HEAD>
<BODY 
class="mediawiki ltr ns-0 ns-subject page-Algorithmics_of_sudoku skin-monobook">
<DIV id=globalWrapper>
<DIV id=column-content>
<DIV id=content><A id=top></A>
<DIV id=siteNotice>
<SCRIPT 
type=text/javascript>if (wgNotice != '') document.writeln(wgNotice);</SCRIPT>
</DIV>
<H1 class=firstHeading id=firstHeading>Algorithmics of sudoku</H1>
<DIV id=bodyContent>
<H3 id=siteSub>From Wikipedia, the free encyclopedia</H3>
<DIV id=contentSub></DIV>
<DIV id=jump-to-nav>Jump to: <A 
href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#column-one">navigation</A>, 
<A 
href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#searchInput">search</A></DIV><!-- start content -->
<TABLE class="metadata plainlinks ambox ambox-style">
  <TBODY>
  <TR>
    <TD class=mbox-image>
      <DIV style="WIDTH: 52px"><IMG height=40 alt="" 
      src="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/40px-Edit-clear.svg.png" 
      width=40></DIV></TD>
    <TD class=mbox-text>This article <B>may require <A title=Wikipedia:Cleanup 
      href="http://en.wikipedia.org/wiki/Wikipedia:Cleanup">cleanup</A> to meet 
      Wikipedia's <A title="Wikipedia:Manual of Style" 
      href="http://en.wikipedia.org/wiki/Wikipedia:Manual_of_Style">quality 
      standards</A>.</B> Please <A class="external text" 
      href="http://en.wikipedia.org/w/index.php?title=Algorithmics_of_sudoku&amp;action=edit" 
      rel=nofollow>improve this article</A> if you can. <SMALL><I>(April 
      2007)</I></SMALL></TD></TR></TBODY></TABLE>
<TABLE class="metadata plainlinks ambox ambox-content">
  <TBODY>
  <TR>
    <TD class=mbox-image>
      <DIV style="WIDTH: 52px"><IMG height=40 alt="" 
      src="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/Ambox_content.png" 
      width=40></DIV></TD>
    <TD class=mbox-text>This article <B>may contain <A 
      title="Wikipedia:No original research" 
      href="http://en.wikipedia.org/wiki/Wikipedia:No_original_research">original 
      research</A> or <A title=Wikipedia:Verifiability 
      href="http://en.wikipedia.org/wiki/Wikipedia:Verifiability">unverified 
      claims</A></B>. Please <A class="external text" 
      href="http://en.wikipedia.org/w/index.php?title=Algorithmics_of_sudoku&amp;action=edit" 
      rel=nofollow>improve the article</A> by adding <A class=mw-redirect 
      title=Wikipedia:References 
      href="http://en.wikipedia.org/wiki/Wikipedia:References">references</A>. 
      See the <A title="Talk:Algorithmics of sudoku" 
      href="http://en.wikipedia.org/wiki/Talk:Algorithmics_of_sudoku">talk 
      page</A> for details. <SMALL><I>(September 
2007)</I></SMALL></TD></TR></TBODY></TABLE>
<P>The <A title="Class (set theory)" 
href="http://en.wikipedia.org/wiki/Class_(set_theory)">class</A> of <B><A 
title=Sudoku href="http://en.wikipedia.org/wiki/Sudoku">Sudoku</A></B> <A 
title=Puzzle href="http://en.wikipedia.org/wiki/Puzzle">puzzles</A> consists of 
a partially completed row-column grid of cells partitioned into <I>N</I> 
<I>regions</I> or <I>zones</I> each of size <I>N</I> cells, to be filled in 
using a prescribed set of <I>N</I> distinct symbols (typically the numbers {1, 
..., <I>N</I>}), so that each row, column and region contains exactly one of 
each element of the set. The puzzle can be solved using a variety of algorithms. 
This page provides algorithms only.</P>
<TABLE class=toc id=toc>
  <TBODY>
  <TR>
    <TD>
      <DIV id=toctitle>
      <H2>Contents</H2></DIV>
      <UL>
        <LI class="toclevel-1 tocsection-1"><A 
        href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#Solving_sudokus_by_backtracking"><SPAN 
        class=tocnumber>1</SPAN> <SPAN class=toctext>Solving sudokus by 
        backtracking</SPAN></A> 
        <LI class="toclevel-1 tocsection-2"><A 
        href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#Exact_Cover_in_solving_sudokus"><SPAN 
        class=tocnumber>2</SPAN> <SPAN class=toctext>Exact Cover in solving 
        sudokus</SPAN></A> 
        <LI class="toclevel-1 tocsection-3"><A 
        href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#Solving_sudokus_by_a_brute-force_algorithm"><SPAN 
        class=tocnumber>3</SPAN> <SPAN class=toctext>Solving sudokus by a 
        brute-force algorithm</SPAN></A> 
        <LI class="toclevel-1 tocsection-4"><A 
        href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#Solving_sudokus_via_stochastic_search_.2F_optimization_methods"><SPAN 
        class=tocnumber>4</SPAN> <SPAN class=toctext>Solving sudokus via 
        stochastic search / optimization methods</SPAN></A> 
        <LI class="toclevel-1 tocsection-5"><A 
        href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#Solving_sudokus_by_Constraint_Programming_.28CP.29"><SPAN 
        class=tocnumber>5</SPAN> <SPAN class=toctext>Solving sudokus by 
        Constraint Programming (CP)</SPAN></A> 
        <LI class="toclevel-1 tocsection-6"><A 
        href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#Algorithmic_Search_for_Symmetrical_Sudokus_with_Few_Givens"><SPAN 
        class=tocnumber>6</SPAN> <SPAN class=toctext>Algorithmic Search for 
        Symmetrical Sudokus with Few Givens</SPAN></A> 
        <LI class="toclevel-1 tocsection-7"><A 
        href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#Solving_a_blank_sudoku_grid"><SPAN 
        class=tocnumber>7</SPAN> <SPAN class=toctext>Solving a blank sudoku 
        grid</SPAN></A> 
        <LI class="toclevel-1 tocsection-8"><A 
        href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#Standard_Sudoku_solver_and_enumerator"><SPAN 
        class=tocnumber>8</SPAN> <SPAN class=toctext>Standard Sudoku solver and 
        enumerator</SPAN></A> 
        <UL>
          <LI class="toclevel-2 tocsection-9"><A 
          href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#Key_modifications_to_the_algorithm"><SPAN 
          class=tocnumber>8.1</SPAN> <SPAN class=toctext>Key modifications to 
          the algorithm</SPAN></A> 
          <LI class="toclevel-2 tocsection-10"><A 
          href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#Discussion_of_the_modified_algorithm"><SPAN 
          class=tocnumber>8.2</SPAN> <SPAN class=toctext>Discussion of the 
          modified algorithm</SPAN></A> 
          <LI class="toclevel-2 tocsection-11"><A 
          href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#Example_of_a_back-tracking_Sudoku_solver_.28in_the_Ruby_programming_language.29"><SPAN 
          class=tocnumber>8.3</SPAN> <SPAN class=toctext>Example of a 
          back-tracking Sudoku solver (in the Ruby programming 
          language)</SPAN></A> 
          <LI class="toclevel-2 tocsection-12"><A 
          href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#Example_of_a_brute_force_Sudoku_solver_.28in_C.29"><SPAN 
          class=tocnumber>8.4</SPAN> <SPAN class=toctext>Example of a brute 
          force Sudoku solver (in C)</SPAN></A> 
          <LI class="toclevel-2 tocsection-13"><A 
          href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#Example_of_Sudoku_solver_.28in_Prolog.29"><SPAN 
          class=tocnumber>8.5</SPAN> <SPAN class=toctext>Example of Sudoku 
          solver (in Prolog)</SPAN></A> </LI></UL>
        <LI class="toclevel-1 tocsection-14"><A 
        href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#Exceptionally_difficult_Sudokus_.28Hardest_Sudokus.29"><SPAN 
        class=tocnumber>9</SPAN> <SPAN class=toctext>Exceptionally difficult 
        Sudokus (Hardest Sudokus)</SPAN></A> 
        <LI class="toclevel-1 tocsection-15"><A 
        href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#References"><SPAN 
        class=tocnumber>10</SPAN> <SPAN class=toctext>References</SPAN></A> 
        <LI class="toclevel-1 tocsection-16"><A 
        href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#External_links"><SPAN 
        class=tocnumber>11</SPAN> <SPAN class=toctext>External links</SPAN></A> 
        </LI></UL></TD></TR></TBODY></TABLE>
<SCRIPT type=text/javascript>
//<![CDATA[
if (window.showTocToggle) { var tocShowText = "show"; var tocHideText = "hide"; showTocToggle(); } 
//]]>
</SCRIPT>

<H2><SPAN class=editsection>[<A 
title="Edit section: Solving sudokus by backtracking" 
href="http://en.wikipedia.org/w/index.php?title=Algorithmics_of_sudoku&amp;action=edit&amp;section=1">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Solving_sudokus_by_backtracking>Solving sudokus by 
backtracking</SPAN></H2>
<P>The basic <A title=Backtracking 
href="http://en.wikipedia.org/wiki/Backtracking">backtracking</A> algorithm can 
be adapted to solve sudokus. This is straightforward. Say a <I>zone</I> is a 
subset of <I>N</I> boxes of an <I>N x N</I> grid, which must contain the numbers 
from 1 to <I>N</I>. A standard sudoku contains 27 zones, namely 9 rows, 9 
columns and 9 squares that are 3 x 3. In a jigsaw sudoku, the square zones are 
replaced by zones having irregular boundaries, like a jigsaw piece.</P>
<P>One possible algorithm that uses backtracking to solve such sudokus 
constructs a graph on <SPAN class=texhtml><I>N</I><SUP>2</SUP></SPAN> vertices, 
one vertex for each box of the grid. Two vertices are connected by an edge if 
there exists a zone containing the two boxes. The problem is then equivalent to 
coloring this graph with <I>N</I> colors, where adjacent vertices may not have 
the same color. This is done by starting with an empty assignment of colors and 
assigning colors to vertices one after another, using some fixed order of the 
vertices. Whenever a color is being assigned, we check whether it is compatible 
with the existing assignments, i.e. whether the new color occurs among the 
neighbors of that vertex. If it doesn't, then we may assign it to the vertex and 
try to process another vertex. We backtrack once all <I>N</I> colors have been 
tried for a given vertex. If all vertices have been assigned a color, then we 
have found a solution. There are of course much more sophisticated algorithms to 
solve <A title="Graph coloring" 
href="http://en.wikipedia.org/wiki/Graph_coloring">graph coloring</A>. If the 
sudoku contains initial data, i.e. some boxes have already been filled, then 
these go into the color assignment before backtracking begins and the vertex 
sequence includes only the empty boxes.</P>
<P>The above algorithm was used to solve a 10x10 jigsaw sudoku that was proposed 
on <I>Les-Mathematiques.net</I> A link to the proposal may be found in the 
section for <A class=mw-redirect title="Algorithmics of Sudoku" 
href="http://en.wikipedia.org/wiki/Algorithmics_of_Sudoku#External_links">external 
links</A>. The first section of the program defines the 10 jigsaw pieces 
(zones), the second the row and column zones. Thereafter the graph is 
constructed as an adjacency list. The search procedure prints completed 
solutions (when all 100 boxes have been assigned). Otherwise it computes the set 
of colors present among the neighbors of the next vertex to be processed, and 
recursively tries those assignments that do not conflict with this set. The 
search starts with an empty assignment.</P>
<P>A simple trick to narrow the range of the numbers of a box can be used in 
improving backtracking solutions efficiently. For a sudoku with some filled 
boxes, the numbers of the blank boxes are often restricted to be in a small 
subset of <I>N</I> because they are required not to be conflict with other boxes 
in the correspondent zones. For example, a zone like [1, 2, 3, 
{4,5},{4,6},{4,5,6},{4,5,6,7},{7,8},{8,9}] might exist after the numbers in the 
filled boxes are used to <I>clean up</I> a sudoku. Note that there are three 
boxes, {4,5},{4,6} and {4,5,6}, with three possible numbers, 4,5 and 6. That 
means, 4,5 and 6 would definitely occupy the three boxes and other boxes should 
not have those numbers. Therefore, instead of backtrack the graph instantly, we 
can at first narrow the range of other boxes by removing the numbers 4,5 and 6 
and get the result zone as [1, 2, 3, {4,5}, {4,6}, {4,5,6}, 7, 8, 9]. Using this 
trick, common Sudoku puzzles seldom needs many backtrackings to find the 
solution.</P>
<H2><SPAN class=editsection>[<A 
title="Edit section: Exact Cover in solving sudokus" 
href="http://en.wikipedia.org/w/index.php?title=Algorithmics_of_sudoku&amp;action=edit&amp;section=2">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Exact_Cover_in_solving_sudokus>Exact Cover in solving 
sudokus</SPAN></H2>
<DIV class="rellink boilerplate seealso">See also: <A title="Exact cover" 
href="http://en.wikipedia.org/wiki/Exact_cover#Sudoku">Exact 
cover#Sudoku</A></DIV>
<P>Sudoku can be described as an instance of the <A title="Exact cover" 
href="http://en.wikipedia.org/wiki/Exact_cover">exact cover</A> problem. This 
allows both for a very elegant description of the problem and an efficient 
solution using a backtracking algorithm.</P>
<P>In an exact cover problem, there is given a universe <I>U</I> of elements and 
a collection <IMG class=tex alt=\mathcal{S} 
src="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/3791545a70a6e462451c97ad925d43a4.png"> 
of subsets of <I>U</I>. The task is to find a <A title=Subset 
href="http://en.wikipedia.org/wiki/Subset">subcollection</A> <IMG class=tex 
alt=\mathcal{S}^* 
src="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/a4c9601f599d2f9c9889246bad96f68b.png"> 
of <IMG class=tex alt=\mathcal{S} 
src="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/3791545a70a6e462451c97ad925d43a4.png"> 
such that every element in <I>U</I> is an <A title="Element (mathematics)" 
href="http://en.wikipedia.org/wiki/Element_(mathematics)">element</A> of exactly 
one set in <IMG class=tex alt=\mathcal{S}^* 
src="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/a4c9601f599d2f9c9889246bad96f68b.png">.</P>
<P>The challenge in applying the exact cover problem to sudoku is to find a 
definition for the elements of <I>U</I> such that every valid sudoku solution 
must contain every element of <I>U</I> exactly once, and to find a definition 
for the elements of <IMG class=tex alt=\mathcal{S} 
src="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/3791545a70a6e462451c97ad925d43a4.png"> 
(subsets of <I>U</I>) such that if the union of a disjoint collection of these 
elements gives <I>U</I>, then the elements specify a completely filled-in sudoku 
grid which satisfies every constraint.</P>
<P>Let <I>S</I> = {<I>s<SUB>11</SUB></I>, <I>s<SUB>12</SUB></I>, …, 
<I>s<SUB>19</SUB></I>, <I>s<SUB>21</SUB></I>, …, <I>s<SUB>99</SUB></I>} be the 
set of squares of the sudoku grid.</P>
<P>Let <I>r<SUB>i</SUB></I> = {<I>s<SUB>i1</SUB></I>, <I>s<SUB>i2</SUB></I>, …, 
<I>s<SUB>i9</SUB></I>} ⊆ <I>S</I> be the set of squares belonging to row 
<I>i</I>, and let <I>R</I> = {<I>r<SUB>1</SUB></I>, <I>r<SUB>2</SUB></I>, …, 
<I>r<SUB>9</SUB></I>} be the set of rows.</P>
<P>Let <I>c<SUB>j</SUB></I> = {<I>s<SUB>1j</SUB></I>, <I>s<SUB>2j</SUB></I>, …, 
<I>s<SUB>9j</SUB></I>} ⊆ <I>S</I> be the set of squares belonging to column 
<I>j</I>, and let <I>C</I> = {<I>c<SUB>1</SUB></I>, <I>c<SUB>2</SUB></I>, …, 
<I>c<SUB>9</SUB></I>} be the set of columns.</P>
<P>Clearly, for each row <I>i</I> and column <I>j</I>, {<I>s<SUB>ij</SUB></I>} = 
<I>r<SUB>i</SUB> ∩ c<SUB>j</SUB></I>.</P>
<P>Let <I>b<SUB>k</SUB></I> be the set of squares belonging to block <I>k</I>, 
and let <I>B</I> = {<I>b<SUB>1</SUB></I>, <I>b<SUB>2</SUB></I>, …, 
<I>b<SUB>9</SUB></I>} be the set of blocks.</P>
<P>Thus, <I>b<SUB>1</SUB></I> is the intersection of rows 1 to 3 with columns 1 
to 3, <I>b<SUB>2</SUB></I> is the intersection of rows 1 to 3 with columns 4 to 
6, …, and <I>b<SUB>9</SUB></I> is the intersection of rows 7 to 9 with columns 7 
to 9. For example,</P>
<DL>
  <DD><I>b<SUB>2</SUB></I> = {<I>s<SUB>14</SUB>, s<SUB>15</SUB>, s<SUB>16</SUB>, 
  s<SUB>24</SUB>, s<SUB>25</SUB>, s<SUB>26</SUB>, s<SUB>34</SUB>, 
  s<SUB>35</SUB>, s<SUB>36</SUB></I>}. </DD></DL>
<P>Finally, we are ready to define a universe <I>U</I> and a collection <IMG 
class=tex alt=\mathcal{S} 
src="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/3791545a70a6e462451c97ad925d43a4.png"> 
of subsets of <I>U</I> which exactly mirror the required constraints on the 
placement of values in the squares of the sudoku grid. A solution to the exact 
cover problem is a collection <IMG class=tex alt=\mathcal{S}^* 
src="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/a4c9601f599d2f9c9889246bad96f68b.png"> 
of disjoint subsets of <I>U</I> whose union is exactly <I>U</I>: each element of 
<I>U</I> appears in exactly one element of <IMG class=tex alt=\mathcal{S}^* 
src="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/a4c9601f599d2f9c9889246bad96f68b.png">. 
How can this be applied to sudoku? We need to find a set of objects each of 
which appears exactly once in every finished sudoku puzzle. Every square of the 
grid must appear exactly once. Every row, column, and square must contain each 
value exactly once. Each of these constraints involves pairs: pairs of rows and 
columns, pairs of rows and values, pairs of columns and values, and pairs of 
blocks and values. Our universe is going to be made up of pairs.</P>
<P>Consider the <A title="Cartesian product" 
href="http://en.wikipedia.org/wiki/Cartesian_product">Cartesian products</A> 
<I>R×C</I>, <I>R×V</I>, <I>C×V</I>, and <I>B×V</I>. Each contains 81 pairs. For 
example <I>R×C</I> = {<I>(r<SUB>1</SUB>, c<SUB>1</SUB>), ..., (r<SUB>9</SUB>, 
c<SUB>9</SUB>)</I>}. The universe <I>U</I> is the 324 element union of these 
four Cartesian products. As it happens, every valid sudoku solution contains 
exactly these 324 pairs, no more, no less. But this set of pairs does not 
represent a specific solution. It represents <I>every</I> valid solution to the 
blank sudoku grid.</P>
<P>To represent a specific solution, we need to assign a specific value to each 
square. Let <I>S<SUB>ijkl</SUB></I> denote the subset of <I>U</I> containing 
<I>(r<SUB>i</SUB>, c<SUB>j</SUB>), (r<SUB>i</SUB>, v<SUB>l</SUB>), 
(c<SUB>j</SUB>, v<SUB>l</SUB>), and (b<SUB>k</SUB>, v<SUB>l</SUB>)</I>. This 
subset denotes the assignment of value <I>l</I> to square <I>s<SUB>ij</SUB></I>. 
The collection <IMG class=tex alt=\mathcal{S} 
src="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/3791545a70a6e462451c97ad925d43a4.png"> 
contains exactly those subsets <I>S<SUB>ijkl</SUB></I> of <I>U</I> in which 
square <I>ij</I> is an element of block <I>k</I>, i.e., <I>s<SUB>ij</SUB></I> ∈ 
<I>b<SUB>k</SUB></I>. Since <I>k</I> is completely dependent on <I>i</I> and 
<I>j</I>, there are 9×9×9 = 729 such subsets in <IMG class=tex alt=\mathcal{S} 
src="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/3791545a70a6e462451c97ad925d43a4.png">.</P>
<P>An incomplete sudoku grid is represented by a disjoint collection <IMG 
class=tex alt="\mathcal{S}'" 
src="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/1d09f984637faf4e8229041fabd96fee.png"> 
of subsets <I>S<SUB>ijkl</SUB></I> of <I>U</I> which does not specify a value 
for every square. Since the collection is disjoint (each element of <I>U</I> 
appears in at most one subset), we know it does not violate any of the sudoku 
constraints.</P>
<P>Now, applying the exact cover problem, we find members of <IMG class=tex 
alt=\mathcal{S} 
src="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/3791545a70a6e462451c97ad925d43a4.png"> 
disjoint from each other and from each member of <IMG class=tex 
alt="\mathcal{S}'" 
src="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/1d09f984637faf4e8229041fabd96fee.png">, 
resulting in the collection <IMG class=tex alt=\mathcal{S}^* 
src="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/a4c9601f599d2f9c9889246bad96f68b.png"> 
of 81 disjoint four-element subsets of <I>U</I> whose union is exactly the 324 
element set <I>U</I>.</P>
<P>This representation of the sudoku problem eliminates all mention of rows, 
columns, blocks, and values from the implementation. Instead, we always work 
with the same collection of 729 four-element subsets of a 324 element universe. 
These can be represented by the integers 0 to 728, together with a function 
<I>f(i,j)</I> which is true if the subsets corresponding to i and j are 
disjoint. <I>f</I> might be implemented using a 729<SUP>2</SUP> = 531441 element 
(66431 byte) constant bit vector. A specific puzzle is a set of fewer than 81 
integers with <I>f(i,j)</I> true for each pair <I>i,j</I>. Solving the puzzle 
involves repeatedly finding a new integer <I>k</I> which passes <I>f(i,k)</I> 
for each <I>i</I> in the partially completed puzzle, and backtracking when no 
such <I>k</I> can be found.</P>
<P>Obviously, once we find that a specific <I>k</I> fails <I>f(i,k)</I> for some 
<I>i</I>, we need not consider it again so long as <I>i</I> remains in the 
proposed solution. So we keep a list of <I>k</I> values which have not yet 
failed. The length of this list estimates the amount of work required to 
discover that the current proposed solution fails. So at each level of 
recursion, we can look ahead one level to estimate how much work each proposed 
<I>k</I> will involve, and choose the <I>k</I> which returns failure in the 
shortest time.</P>
<P>Although the size of the complete search tree is fixed for a given puzzle, 
this representation of the problem gives a fast test for failure at each level, 
and a way of ordering the search so that the smallest subtrees are searched 
first.</P>
<P>With this approach and an efficient library for solving exact cover problems, 
one can solve 9×9 sudokus in such a short time on a modern PC that measuring the 
computation time becomes challenging.</P>
<H2><SPAN class=editsection>[<A 
title="Edit section: Solving sudokus by a brute-force algorithm" 
href="http://en.wikipedia.org/w/index.php?title=Algorithmics_of_sudoku&amp;action=edit&amp;section=3">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Solving_sudokus_by_a_brute-force_algorithm>Solving 
sudokus by a brute-force algorithm</SPAN></H2>
<P>Some hobbyists have developed computer programs that will solve sudoku 
puzzles using a brute force algorithm. Although it has been established that 
approximately 6.67 x 10<SUP>21</SUP> final grids exist, using a brute force 
algorithm can be a practical method to solve puzzles using a computer program if 
the code is well designed.</P>
<P>An advantage of this method is that if the puzzle is valid, a solution is 
guaranteed. There is not a strong relation between the solving time and the 
degree of difficulty of the puzzle; generating a solution is just a matter of 
waiting until the algorithm advances to the set of numbers that satisfies the 
puzzle. The disadvantage of this method is that it may be comparatively slow 
when compared to computer solution methods modeled after human-style deductive 
methods.</P>
<P>Briefly, a brute force program would solve a puzzle by placing the digit "1" 
in the first cell and checking if it is allowed to be there. If there are no 
violations (checking row, column, and box constraints) then the algorithm 
advances to the next cell, and places a "1" in that cell. When checking for 
violations, it is discovered that the "1" is not allowed, so the value is 
advanced to a "2". If a cell is discovered where none of the 9 digits is 
allowed, then the algorithm leaves that cell blank and moves back to the 
previous cell. The value in that cell is then incremented by one. The algorithm 
is repeated until the allowed value in the 81st cell is discovered. The 
construction of 81 numbers is parsed to form the 9 x 9 solution matrix.</P>
<P>Most Sudoku puzzles will be solved in just a few seconds with this method, 
but there are exceptions. The following puzzle was designed to be a near worst 
case situation for solution by brute force (although it is not regarded as a 
difficult puzzle when solved by other methods).</P>
<DIV class="thumb tright">
<DIV class=thumbinner style="WIDTH: 182px"><A class=image 
href="http://en.wikipedia.org/wiki/File:Sudoku_puzzle_hard_for_brute_force.jpg"><IMG 
class=thumbimage height=160 alt="" 
src="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/180px-Sudoku_puzzle_hard_for_brute_force.jpg" 
width=180></A> 
<DIV class=thumbcaption>
<DIV class=magnify><A class=internal title=Enlarge 
href="http://en.wikipedia.org/wiki/File:Sudoku_puzzle_hard_for_brute_force.jpg"><IMG 
height=11 alt="" 
src="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/magnify-clip.png" 
width=15></A></DIV>"Near worst case" sudoku puzzle for brute force 
solver.</DIV></DIV></DIV>
<P>Solving this puzzle by brute-force requires a large number of iterations 
because it has a low number of clues (17), the top row has no clues at all, and 
the solution has "987654321" as its first row. Thus a brute-force solver will 
spend an enormous amount of time "counting" upward before it arrives at the 
final grid which satisfies the puzzle. If one iteration is defined as one 
attempt to place one value in one cell, then this puzzles requires 641,580,843 
iterations to solve. These iterations do not include the work involved at each 
step to learn if each digit entered is valid or not (required for every 
iteration). Based on the specific construction of the computer code, programmers 
have found the solution time for this puzzle to be between 30 and 45 minutes 
with a computer processor running at 3&nbsp;GHz. Many programmers have developed 
variations of the brute force algorithm which will solve this puzzle in a minute 
or less with a 3&nbsp;GHz computer processor.</P>
<P>An extremely simplistic brute force algorithm written in the C language 
running on a 2.2&nbsp;GHz processor solved the above puzzle in just over a 
minute. Hence, the choice of programming language is obviously important. 
Further, a trivial modification to that simplistic algorithm is to rotate the 
puzzle prior to beginning the iterations allowing for the easiest angle of 
attack. By looking at the puzzle from four different angles, the program can 
quickly deduce which angle is likely to result in the most iterations. With that 
one modification, the same 2.2&nbsp;GHz processor was able to solve the above 
puzzle in about a half a second.</P>
<P>One programmer has created charts of the progression of a pointer as it 
advances through the 81 positions of a sudoku using a brute force algorithm. An 
example is the chart for the solution to a sudoku "Star Burst Leo" shown 
here.<SUP class=reference id=cite_ref-0><A 
href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#cite_note-0"><SPAN>[</SPAN>1<SPAN>]</SPAN></A></SUP><SUP 
class=reference id=cite_ref-1><A 
href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#cite_note-1"><SPAN>[</SPAN>2<SPAN>]</SPAN></A></SUP></P>
<DIV class="thumb tleft">
<DIV class=thumbinner style="WIDTH: 182px"><A class=image 
href="http://en.wikipedia.org/wiki/File:Star_Burst_Leo_Sudoku.JPG"><IMG 
class=thumbimage height=160 alt="" 
src="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/180px-Star_Burst_Leo_Sudoku.jpg" 
width=180></A> 
<DIV class=thumbcaption>
<DIV class=magnify><A class=internal title=Enlarge 
href="http://en.wikipedia.org/wiki/File:Star_Burst_Leo_Sudoku.JPG"><IMG 
height=11 alt="" 
src="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/magnify-clip.png" 
width=15></A></DIV>"Star Burst Leo" Sudoku</DIV></DIV></DIV>
<DIV class="thumb tnone">
<DIV class=thumbinner style="WIDTH: 302px"><A class=image 
href="http://en.wikipedia.org/wiki/File:Star_Burst_Leo_Chart.JPG"><IMG 
class=thumbimage height=218 alt="" 
src="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/300px-Star_Burst_Leo_Chart.jpg" 
width=300></A> 
<DIV class=thumbcaption>
<DIV class=magnify><A class=internal title=Enlarge 
href="http://en.wikipedia.org/wiki/File:Star_Burst_Leo_Chart.JPG"><IMG height=11 
alt="" 
src="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/magnify-clip.png" 
width=15></A></DIV>Chart of cell position for solution to "Star Burst Leo" when 
solved by a brute force algorithm</DIV></DIV></DIV>
<H2><SPAN class=editsection>[<A 
title="Edit section: Solving sudokus via stochastic search / optimization methods" 
href="http://en.wikipedia.org/w/index.php?title=Algorithmics_of_sudoku&amp;action=edit&amp;section=4">edit</A>]</SPAN> 
<SPAN class=mw-headline 
id=Solving_sudokus_via_stochastic_search_.2F_optimization_methods>Solving 
sudokus via stochastic search / optimization methods</SPAN></H2>
<P>Some researchers have also shown how sudoku can be solved using 
stochastic—i.e. random-based—search.<SUP class=reference 
id=cite_ref-Lewis.2C_R_.282007.29_pp_387-401_2-0><A 
href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#cite_note-Lewis.2C_R_.282007.29_pp_387-401-2"><SPAN>[</SPAN>3<SPAN>]</SPAN></A></SUP></P>
<P>Such a method could work as follows: first, start by randomly assigning 
numbers to the blank cells in the grid, and calculate the number of errors. Now 
start to "shuffle" these inserted numbers around the grid until the number of 
mistakes has been reduced to zero. A solution to the puzzle will then have been 
found. Approaches for shuffling the numbers include <A 
title="Simulated annealing" 
href="http://en.wikipedia.org/wiki/Simulated_annealing">simulated annealing</A>, 
and <A title="Tabu search" href="http://en.wikipedia.org/wiki/Tabu_search">tabu 
search</A>.</P>
<P>The advantage of this type of method is that the puzzle does not have to be 
"logic-solvable" in order for the algorithm to be able to solve it. In other 
words, unlike other methods, the puzzles that are given to this algorithm do not 
have to be specially constructed so that they provide sufficient clues for 
filling the grid using forward chaining logic only. In fact, the only 
prerequisite for the stochastic search algorithm to work is that puzzle has at 
least one solution.</P>
<P>Stochastic-based optimisation algorithms are known to be quite fast, though 
they are perhaps not as fast as some logic-based techniques with logic solvable 
puzzles. Depending on the type of instance given to the algorithm, generally 9x9 
puzzles will be solved in less than 1 second on a typical year-2000 laptop; 
16x16 puzzles will take around 10–15 seconds. In the paper by <A class=new 
title="Meir Perez (page does not exist)" 
href="http://en.wikipedia.org/w/index.php?title=Meir_Perez&amp;action=edit&amp;redlink=1">Meir 
Perez</A> and <A title="Tshilidzi Marwala" 
href="http://en.wikipedia.org/wiki/Tshilidzi_Marwala">Tshilidzi Marwala</A> the 
Sudoku puzzle is successfully solved using stochastic search techniques and 
these were: <A title="Cultural algorithm" 
href="http://en.wikipedia.org/wiki/Cultural_algorithm">cultural algorithm</A>, 
<A title="Quantum annealing" 
href="http://en.wikipedia.org/wiki/Quantum_annealing">quantum annealing</A> and 
the Hybrid method that combines <A title="Genetic algorithm" 
href="http://en.wikipedia.org/wiki/Genetic_algorithm">genetic algorithm</A> with 
<A title="Simulated annealing" 
href="http://en.wikipedia.org/wiki/Simulated_annealing">simulated 
annealing</A>.<SUP class=reference 
id=cite_ref-Perez.2C_Meir_and_Marwala.2C_Tshilidzi_.282008.29_3-0><A 
href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#cite_note-Perez.2C_Meir_and_Marwala.2C_Tshilidzi_.282008.29-3"><SPAN>[</SPAN>4<SPAN>]</SPAN></A></SUP>.</P>
<P>Finally, note that it is also possible to express a Sudoku as an <A 
class=mw-redirect title="Integer linear programming" 
href="http://en.wikipedia.org/wiki/Integer_linear_programming">integer linear 
programming</A> problem. Such approaches seem to get close to a solution quite 
quickly, and can then use branching towards the end. The <A 
title="Simplex algorithm" 
href="http://en.wikipedia.org/wiki/Simplex_algorithm">Simplex algorithm</A> 
seems able to handle situations with no solutions or multiple solutions quite 
well.</P>
<H2><SPAN class=editsection>[<A 
title="Edit section: Solving sudokus by Constraint Programming (CP)" 
href="http://en.wikipedia.org/w/index.php?title=Algorithmics_of_sudoku&amp;action=edit&amp;section=5">edit</A>]</SPAN> 
<SPAN class=mw-headline 
id=Solving_sudokus_by_Constraint_Programming_.28CP.29>Solving sudokus by 
Constraint Programming (CP)</SPAN></H2>
<P>Sudoku is a constraint problem. An article by Helmut Simoni at Imperial 
College London <SUP class=reference id=cite_ref-4><A 
href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#cite_note-4"><SPAN>[</SPAN>5<SPAN>]</SPAN></A></SUP> 
describes in great detail many different reasoning algorithm available in the 
form of constraints which can be applied to model and solve the problem. It 
requires 81 finite domain variables and 21 constraints. Any constraint solver 
will have an example how to model and solve Sudoku problem (e.g.<SUP 
class=reference id=cite_ref-5><A 
href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#cite_note-5"><SPAN>[</SPAN>6<SPAN>]</SPAN></A></SUP>). 
It will solve the problem in miliseconds. Moreover, the constraint program 
modeling and solving Sudoku will in most solvers have less than 100 lines of 
code. If the code employs a strong reasoning algorithm (still polynomial 
complexity) then only some of the hardest instances (diabolic) requires further 
code which employs a search routine.</P>
<H2><SPAN class=editsection>[<A 
title="Edit section: Algorithmic Search for Symmetrical Sudokus with Few Givens" 
href="http://en.wikipedia.org/w/index.php?title=Algorithmics_of_sudoku&amp;action=edit&amp;section=6">edit</A>]</SPAN> 
<SPAN class=mw-headline 
id=Algorithmic_Search_for_Symmetrical_Sudokus_with_Few_Givens>Algorithmic Search 
for Symmetrical Sudokus with Few Givens</SPAN></H2>
<P>Computer algorithms work through increasingly more cycles when searching for 
sudokus with 20 clues or fewer. Indeed puzzles with 17 clues are notoriously 
difficult to find. When the constraint of symmetry is applied, the expected 
search time will dramatically increase yet further.<SUP class=reference 
id=cite_ref-6><A 
href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#cite_note-6"><SPAN>[</SPAN>7<SPAN>]</SPAN></A></SUP> 
When working with 19 clues or fewer, there are some classes of symmetry for 
which no sudoku has been found, and none may exist.<SUP class=reference 
id=cite_ref-7><A 
href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#cite_note-7"><SPAN>[</SPAN>8<SPAN>]</SPAN></A></SUP> 
The table below shows the seven classes of symmetry and whether one or more 
sudokus has been discovered for the range of 20 clues and fewer.</P>
<TABLE cellSpacing=0 cellPadding=2 align=center border=1>
  <CAPTION><B>Discovery of Sudokus with 20 Clues or Fewer for each Class of 
  Symmetry</B></CAPTION>
  <TBODY>
  <TR>
    <TH style="BACKGROUND: #efefef">givens</TH>
    <TH style="BACKGROUND: #efefef">Vertical or Horizontal</TH>
    <TH style="BACKGROUND: #efefef">Vertical and Horizontal</TH>
    <TH style="BACKGROUND: #efefef">180° Rotational</TH>
    <TH style="BACKGROUND: #efefef">Full 90° Rotational</TH>
    <TH style="BACKGROUND: #efefef">Diagonal One Axis</TH>
    <TH style="BACKGROUND: #efefef">Diagonal Both Axes</TH>
    <TH style="BACKGROUND: #efefef">Full Dihedral (Vertical and Horizontal and 
      Full Rotational)</TH></TR>
  <TR>
    <TD>20</TD>
    <TD style="BACKGROUND: #c3fdb8">Yes</TD>
    <TD style="BACKGROUND: #c3fdb8">Yes</TD>
    <TD style="BACKGROUND: #c3fdb8">Yes</TD>
    <TD style="BACKGROUND: #c3fdb8">Yes</TD>
    <TD style="BACKGROUND: #c3fdb8">Yes</TD>
    <TD style="BACKGROUND: #c3fdb8">Yes</TD>
    <TD style="BACKGROUND: #c3fdb8">Yes</TD></TR>
  <TR>
    <TD>19</TD>
    <TD style="BACKGROUND: #c3fdb8">Yes</TD>
    <TD style="BACKGROUND: #c3fdb8">Yes</TD>
    <TD style="BACKGROUND: #c3fdb8">Yes</TD>
    <TD style="BACKGROUND: #efefef">*</TD>
    <TD style="BACKGROUND: #c3fdb8">Yes</TD>
    <TD style="BACKGROUND: #c3fdb8">Yes</TD>
    <TD style="BACKGROUND: #efefef">*</TD></TR>
  <TR>
    <TD>18</TD>
    <TD style="BACKGROUND: #c3fdb8">Yes</TD>
    <TD>No</TD>
    <TD style="BACKGROUND: #c3fdb8">Yes</TD>
    <TD style="BACKGROUND: #efefef">*</TD>
    <TD style="BACKGROUND: #c3fdb8">Yes</TD>
    <TD style="BACKGROUND: #c3fdb8">Yes</TD>
    <TD style="BACKGROUND: #efefef">*</TD></TR>
  <TR>
    <TD>17</TD>
    <TD>No</TD>
    <TD>No</TD>
    <TD>No</TD>
    <TD>No</TD>
    <TD style="BACKGROUND: #c3fdb8">Yes</TD>
    <TD>No</TD>
    <TD>No</TD></TR></TBODY></TABLE>
<P><SMALL>(asterisk indicates this number of givens does not have a pattern with 
this class of symmetry)</SMALL></P>
<P>Two examples of symmetrical sudokus with a small number of givens are shown 
here:</P>
<DIV class="thumb tleft">
<DIV class=thumbinner style="WIDTH: 182px"><A class=image 
href="http://en.wikipedia.org/wiki/File:Symmetrical_H_and_V_19_clue.JPG"><IMG 
class=thumbimage height=160 alt="" 
src="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/180px-Symmetrical_H_and_V_19_clue.jpg" 
width=180></A> 
<DIV class=thumbcaption>
<DIV class=magnify><A class=internal title=Enlarge 
href="http://en.wikipedia.org/wiki/File:Symmetrical_H_and_V_19_clue.JPG"><IMG 
height=11 alt="" 
src="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/magnify-clip.png" 
width=15></A></DIV>A 19-Clue Sudoku with Horizontal and Vertical 
Symmetry.</DIV></DIV></DIV>
<DIV class="thumb tnone">
<DIV class=thumbinner style="WIDTH: 182px"><A class=image 
href="http://en.wikipedia.org/wiki/File:Symmetrical_18_clue_sudoku_01.JPG"><IMG 
class=thumbimage height=160 alt="" 
src="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/180px-Symmetrical_18_clue_sudoku_01.jpg" 
width=180></A> 
<DIV class=thumbcaption>
<DIV class=magnify><A class=internal title=Enlarge 
href="http://en.wikipedia.org/wiki/File:Symmetrical_18_clue_sudoku_01.JPG"><IMG 
height=11 alt="" 
src="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/magnify-clip.png" 
width=15></A></DIV>An 18-Clue Sudoku with Symmetry on Both Diagonal 
Axes.</DIV></DIV></DIV>
<P><BR></P>
<H2><SPAN class=editsection>[<A 
title="Edit section: Solving a blank sudoku grid" 
href="http://en.wikipedia.org/w/index.php?title=Algorithmics_of_sudoku&amp;action=edit&amp;section=7">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Solving_a_blank_sudoku_grid>Solving a blank sudoku 
grid</SPAN></H2>
<P>Although sudoku grids that come with some of their cells pre-filled can often 
be quite challenging to solve, blank sudoku grids can actually be solved very 
quickly. Perhaps the easiest way of doing this is to produce the <I>root 
solution</I>, which can be achieved using the following very simple, polynomial 
time algorithm<SUP class=reference 
id=cite_ref-Lewis.2C_R_.282007.29_pp_387-401_2-1><A 
href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#cite_note-Lewis.2C_R_.282007.29_pp_387-401-2"><SPAN>[</SPAN>3<SPAN>]</SPAN></A></SUP></P>
<P>For the standard n<SUP>2</SUP> x n<SUP>2</SUP> grid this algorithm 
(java-implementation) is as follows:</P>
<DIV class=mw-geshi dir=ltr style="TEXT-ALIGN: left">
<DIV class="java source-java" style="FONT-FAMILY: monospace"><PRE class=de1><SPAN class=kw1>final</SPAN> <SPAN class=kw4>int</SPAN> n <SPAN class=sy0>=</SPAN> <SPAN class=nu0>3</SPAN><SPAN class=sy0>;</SPAN>
<SPAN class=kw1>final</SPAN> <SPAN class=kw4>int</SPAN><SPAN class=br0>[</SPAN><SPAN class=br0>]</SPAN><SPAN class=br0>[</SPAN><SPAN class=br0>]</SPAN> field <SPAN class=sy0>=</SPAN> <SPAN class=kw1>new</SPAN> <SPAN class=kw4>int</SPAN><SPAN class=br0>[</SPAN>n<SPAN class=sy0>*</SPAN>n<SPAN class=br0>]</SPAN><SPAN class=br0>[</SPAN>n<SPAN class=sy0>*</SPAN>n<SPAN class=br0>]</SPAN><SPAN class=sy0>;</SPAN>
<SPAN class=kw4>int</SPAN> x <SPAN class=sy0>=</SPAN> <SPAN class=nu0>0</SPAN><SPAN class=sy0>;</SPAN>
<SPAN class=kw1>for</SPAN><SPAN class=br0>(</SPAN><SPAN class=kw4>int</SPAN> i <SPAN class=sy0>=</SPAN> <SPAN class=nu0>0</SPAN><SPAN class=sy0>;</SPAN> i <SPAN class=sy0>&lt;</SPAN> n<SPAN class=sy0>;</SPAN> i<SPAN class=sy0>++</SPAN>, x<SPAN class=sy0>++</SPAN><SPAN class=br0>)</SPAN>
	<SPAN class=kw1>for</SPAN><SPAN class=br0>(</SPAN><SPAN class=kw4>int</SPAN> j <SPAN class=sy0>=</SPAN> <SPAN class=nu0>0</SPAN><SPAN class=sy0>;</SPAN> j <SPAN class=sy0>&lt;</SPAN> n<SPAN class=sy0>;</SPAN> j<SPAN class=sy0>++</SPAN>, x<SPAN class=sy0>+=</SPAN>n<SPAN class=br0>)</SPAN>
		<SPAN class=kw1>for</SPAN><SPAN class=br0>(</SPAN><SPAN class=kw4>int</SPAN> k <SPAN class=sy0>=</SPAN> <SPAN class=nu0>0</SPAN><SPAN class=sy0>;</SPAN> k <SPAN class=sy0>&lt;</SPAN> n<SPAN class=sy0>*</SPAN>n<SPAN class=sy0>;</SPAN> k<SPAN class=sy0>++</SPAN>, x<SPAN class=sy0>++</SPAN><SPAN class=br0>)</SPAN>
			field<SPAN class=br0>[</SPAN>n<SPAN class=sy0>*</SPAN>i<SPAN class=sy0>+</SPAN>j<SPAN class=br0>]</SPAN><SPAN class=br0>[</SPAN>k<SPAN class=br0>]</SPAN> <SPAN class=sy0>=</SPAN> <SPAN class=br0>(</SPAN>x <SPAN class=sy0>%</SPAN> <SPAN class=br0>(</SPAN>n<SPAN class=sy0>*</SPAN>n<SPAN class=br0>)</SPAN><SPAN class=br0>)</SPAN> <SPAN class=sy0>+</SPAN> <SPAN class=nu0>1</SPAN><SPAN class=sy0>;</SPAN>
</PRE></DIV></DIV>
<P>The above procedure produces the following 9x9 sudoku:</P><PRE><CODE>+-----------------------+
| 1 2 3 | 4 5 6 | 7 8 9 |
| 4 5 6 | 7 8 9 | 1 2 3 |
| 7 8 9 | 1 2 3 | 4 5 6 |
|-------+-------+-------|
| 2 3 4 | 5 6 7 | 8 9 1 |
| 5 6 7 | 8 9 1 | 2 3 4 |
| 8 9 1 | 2 3 4 | 5 6 7 |
|-------+-------+-------|
| 3 4 5 | 6 7 8 | 9 1 2 |
| 6 7 8 | 9 1 2 | 3 4 5 |
| 9 1 2 | 3 4 5 | 6 7 8 |
+-----------------------+</CODE>
</PRE>
<H2><SPAN class=editsection>[<A 
title="Edit section: Standard Sudoku solver and enumerator" 
href="http://en.wikipedia.org/w/index.php?title=Algorithmics_of_sudoku&amp;action=edit&amp;section=8">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Standard_Sudoku_solver_and_enumerator>Standard Sudoku 
solver and enumerator</SPAN></H2>
<P>This section contains a discussion of a modified backtracking algorithm that 
can be used to create and solve Sudokus even with modest computing resources. A 
standard Sudoku is an <IMG class=tex alt="N \times N" 
src="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/395a9af17f8642e02a32af8637542947.png"> 
Sudoku where <SPAN class=texhtml><I>N</I> = <I>k</I><SUP>2</SUP></SPAN> whose 
zones consist of the rows, columns and <IMG class=tex alt="k \times k" 
src="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/5b5f0112171324a6f9fc5df06f6019dd.png"> 
subsquares as in the classic <IMG class=tex alt="9 \times 9" 
src="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/88577f75f0a4466c6a7c11bd841b65f3.png"> 
Sudoku.</P>
<H3><SPAN class=editsection>[<A 
title="Edit section: Key modifications to the algorithm" 
href="http://en.wikipedia.org/w/index.php?title=Algorithmics_of_sudoku&amp;action=edit&amp;section=9">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Key_modifications_to_the_algorithm>Key modifications 
to the algorithm</SPAN></H3>
<P>Conceptually there is one modification only: the backtracking algorithm sorts 
the vertices by the number of colors already assigned among its neighbors before 
selecting the next vertex to try. The vertex with the largest number of assigned 
colors, and hence, the smallest number of choices, is tried first. (There may be 
more than one such vertex).</P>
<P>The data structures used during the backtracking search are chosen to make 
this easy and fast, although further optimization is possible. The search state 
is stored in three data structures: a hash table whose keys are the vertices and 
whose values are the colors that have been assigned to them. There is an array 
that contains the vertices that have not yet been assigned a color. Finally, 
there is a hash table whose keys are again the vertices and whose values are 
hash tables containing the colors present among the neighbors of the respective 
vertex, as well as a hint as to who assigned them.</P>
<H3><SPAN class=editsection>[<A 
title="Edit section: Discussion of the modified algorithm" 
href="http://en.wikipedia.org/w/index.php?title=Algorithmics_of_sudoku&amp;action=edit&amp;section=10">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Discussion_of_the_modified_algorithm>Discussion of 
the modified algorithm</SPAN></H3>
<P>The algorithm follows this sequence of steps:</P>
<UL>
  <LI>Create the row and column zones, then create the subsquare zones. 
  <LI>Construct the adjacency matrix of the graph. 
  <LI>The search routine: 
  <UL>
    <LI>Print the solution if there are no more vertices to be assigned a color, 
    and return. 
    <LI>Sort the remaining vertices in descending order of colors present among 
    their neighbors. 
    <LI>Pick the/a vertex with the largest number of assigned colors. 
    <LI>Try each of the remaining possible colors recursively. 
    <UL>
      <LI>Update the hash table of vertex neighboring colors to reflect the 
      assignment. 
      <LI>Update the partial solution to reflect the assignment. 
      <LI>Recurse. 
      <LI>Remove the color from the partial solution. 
      <LI>Undo the color assignments from the neighboring colors hash table. 
      </LI></UL></LI></UL>
  <LI>Before the search begins, read the initial color assignment. 
  <LI>Compute the set of vertices to be assigned a color, i.e. not present in 
  the initial assignment. 
  <LI>Compute the initial state of the hash table of neighbor colors. 
  <LI>Start the search. </LI></UL>
<P>The above algorithm can enter into loops. To detect this, add a hash table 
that stores seen configurations. When this happens, terminate the computation 
and indicate FAIL (e.g. by throwing an exception). Repeat with a different seed 
of the random number generator if desired.</P>
<H3><SPAN class=editsection>[<A 
title="Edit section: Example of a back-tracking Sudoku solver (in the Ruby programming language)" 
href="http://en.wikipedia.org/w/index.php?title=Algorithmics_of_sudoku&amp;action=edit&amp;section=11">edit</A>]</SPAN> 
<SPAN class=mw-headline 
id=Example_of_a_back-tracking_Sudoku_solver_.28in_the_Ruby_programming_language.29>Example 
of a back-tracking Sudoku solver (in the Ruby programming language)</SPAN></H3>
<DIV class=mw-geshi dir=ltr style="TEXT-ALIGN: left">
<DIV class="ruby source-ruby" style="FONT-FAMILY: monospace"><PRE class=de1><SPAN class=kw1>def</SPAN> read_matrix
  matrix = <SPAN class=br0>[</SPAN><SPAN class=br0>]</SPAN>
 
  <SPAN class=br0>(</SPAN>0..8<SPAN class=br0>)</SPAN>.<SPAN class=me1>each</SPAN> <SPAN class=br0>{</SPAN> <SPAN class=sy0>|</SPAN>i<SPAN class=sy0>|</SPAN>
    l = <SPAN class=kw3>readline</SPAN>
    matrix<SPAN class=br0>[</SPAN>i<SPAN class=br0>]</SPAN> = <SPAN class=br0>[</SPAN><SPAN class=br0>]</SPAN>
    <SPAN class=br0>(</SPAN>0..8<SPAN class=br0>)</SPAN>.<SPAN class=me1>each</SPAN> <SPAN class=br0>{</SPAN> <SPAN class=sy0>|</SPAN>j<SPAN class=sy0>|</SPAN>
      matrix<SPAN class=br0>[</SPAN>i<SPAN class=br0>]</SPAN><SPAN class=br0>[</SPAN>j<SPAN class=br0>]</SPAN> = l<SPAN class=br0>[</SPAN>j..<SPAN class=me1>j</SPAN><SPAN class=br0>]</SPAN>.<SPAN class=me1>to_i</SPAN>
    <SPAN class=br0>}</SPAN>
  <SPAN class=br0>}</SPAN>
  matrix
<SPAN class=kw1>end</SPAN>
 
<SPAN class=kw1>def</SPAN> permissible<SPAN class=br0>(</SPAN>matrix, i, j<SPAN class=br0>)</SPAN>
  ok = <SPAN class=br0>[</SPAN><SPAN class=kw2>true</SPAN>,<SPAN class=kw2>true</SPAN>,<SPAN class=kw2>true</SPAN>,<SPAN class=kw2>true</SPAN>,<SPAN class=kw2>true</SPAN>,<SPAN class=kw2>true</SPAN>,<SPAN class=kw2>true</SPAN>,<SPAN class=kw2>true</SPAN>,<SPAN class=kw2>true</SPAN><SPAN class=br0>]</SPAN>
  <SPAN class=co1># Same as another in the column isn't permissible...</SPAN>
  <SPAN class=br0>(</SPAN>0..8<SPAN class=br0>)</SPAN>.<SPAN class=me1>each</SPAN> <SPAN class=br0>{</SPAN> <SPAN class=sy0>|</SPAN>i2<SPAN class=sy0>|</SPAN>
    <SPAN class=kw1>next</SPAN> <SPAN class=kw1>if</SPAN> matrix<SPAN class=br0>[</SPAN>i2<SPAN class=br0>]</SPAN><SPAN class=br0>[</SPAN>j<SPAN class=br0>]</SPAN> == 0
    ok<SPAN class=br0>[</SPAN>matrix<SPAN class=br0>[</SPAN>i2<SPAN class=br0>]</SPAN><SPAN class=br0>[</SPAN>j<SPAN class=br0>]</SPAN> <SPAN class=sy0>-</SPAN> 1<SPAN class=br0>]</SPAN> = <SPAN class=kw2>false</SPAN>
  <SPAN class=br0>}</SPAN>
  <SPAN class=co1># Same as another in the row isn't permissible...</SPAN>
  <SPAN class=br0>(</SPAN>0..8<SPAN class=br0>)</SPAN>.<SPAN class=me1>each</SPAN> <SPAN class=br0>{</SPAN> <SPAN class=sy0>|</SPAN>j2<SPAN class=sy0>|</SPAN>
    <SPAN class=kw1>next</SPAN> <SPAN class=kw1>if</SPAN> matrix<SPAN class=br0>[</SPAN>i<SPAN class=br0>]</SPAN><SPAN class=br0>[</SPAN>j2<SPAN class=br0>]</SPAN> == 0
    ok<SPAN class=br0>[</SPAN>matrix<SPAN class=br0>[</SPAN>i<SPAN class=br0>]</SPAN><SPAN class=br0>[</SPAN>j2<SPAN class=br0>]</SPAN> <SPAN class=sy0>-</SPAN> 1<SPAN class=br0>]</SPAN> = <SPAN class=kw2>false</SPAN>
  <SPAN class=br0>}</SPAN>
  <SPAN class=co1># Same as another in the 3x3 block isn't permissible...</SPAN>
  igroup = <SPAN class=br0>(</SPAN>i <SPAN class=sy0>/</SPAN> 3<SPAN class=br0>)</SPAN> <SPAN class=sy0>*</SPAN> 3
  jgroup = <SPAN class=br0>(</SPAN>j <SPAN class=sy0>/</SPAN> 3<SPAN class=br0>)</SPAN> <SPAN class=sy0>*</SPAN> 3
  <SPAN class=br0>(</SPAN>igroup..<SPAN class=br0>(</SPAN>igroup <SPAN class=sy0>+</SPAN> 2<SPAN class=br0>)</SPAN><SPAN class=br0>)</SPAN>.<SPAN class=me1>each</SPAN> <SPAN class=br0>{</SPAN> <SPAN class=sy0>|</SPAN>i2<SPAN class=sy0>|</SPAN>
    <SPAN class=br0>(</SPAN>jgroup..<SPAN class=br0>(</SPAN>jgroup <SPAN class=sy0>+</SPAN> 2<SPAN class=br0>)</SPAN><SPAN class=br0>)</SPAN>.<SPAN class=me1>each</SPAN> <SPAN class=br0>{</SPAN> <SPAN class=sy0>|</SPAN>j2<SPAN class=sy0>|</SPAN>
      <SPAN class=kw1>next</SPAN> <SPAN class=kw1>if</SPAN> matrix<SPAN class=br0>[</SPAN>i2<SPAN class=br0>]</SPAN><SPAN class=br0>[</SPAN>j2<SPAN class=br0>]</SPAN> == 0
      ok<SPAN class=br0>[</SPAN>matrix<SPAN class=br0>[</SPAN>i2<SPAN class=br0>]</SPAN><SPAN class=br0>[</SPAN>j2<SPAN class=br0>]</SPAN> <SPAN class=sy0>-</SPAN> 1<SPAN class=br0>]</SPAN> = <SPAN class=kw2>false</SPAN>
    <SPAN class=br0>}</SPAN>
  <SPAN class=br0>}</SPAN>
  <SPAN class=co1># Convert to the array format...</SPAN>
  ret = <SPAN class=br0>[</SPAN><SPAN class=br0>]</SPAN>
  <SPAN class=br0>(</SPAN>0..8<SPAN class=br0>)</SPAN>.<SPAN class=me1>each</SPAN> <SPAN class=br0>{</SPAN> <SPAN class=sy0>|</SPAN>i2<SPAN class=sy0>|</SPAN> ret.<SPAN class=me1>push</SPAN><SPAN class=br0>(</SPAN>i2 <SPAN class=sy0>+</SPAN> 1<SPAN class=br0>)</SPAN> <SPAN class=kw1>if</SPAN> ok<SPAN class=br0>[</SPAN>i2<SPAN class=br0>]</SPAN> <SPAN class=br0>}</SPAN>
  ret
<SPAN class=kw1>end</SPAN>
 
<SPAN class=kw1>def</SPAN> deep_copy_sudoku<SPAN class=br0>(</SPAN>matrix<SPAN class=br0>)</SPAN>
  newmat = <SPAN class=br0>[</SPAN><SPAN class=br0>]</SPAN>
  <SPAN class=br0>(</SPAN>0..8<SPAN class=br0>)</SPAN>.<SPAN class=me1>each</SPAN> <SPAN class=br0>{</SPAN> <SPAN class=sy0>|</SPAN>i<SPAN class=sy0>|</SPAN>
    newmat<SPAN class=br0>[</SPAN>i<SPAN class=br0>]</SPAN> = <SPAN class=br0>[</SPAN><SPAN class=br0>]</SPAN>
    <SPAN class=br0>(</SPAN>0..8<SPAN class=br0>)</SPAN>.<SPAN class=me1>each</SPAN> <SPAN class=br0>{</SPAN> <SPAN class=sy0>|</SPAN>j<SPAN class=sy0>|</SPAN>
      newmat<SPAN class=br0>[</SPAN>i<SPAN class=br0>]</SPAN><SPAN class=br0>[</SPAN>j<SPAN class=br0>]</SPAN> = matrix<SPAN class=br0>[</SPAN>i<SPAN class=br0>]</SPAN><SPAN class=br0>[</SPAN>j<SPAN class=br0>]</SPAN>
    <SPAN class=br0>}</SPAN>
  <SPAN class=br0>}</SPAN>
  newmat
<SPAN class=kw1>end</SPAN>
 
<SPAN class=kw1>def</SPAN> solve_sudoku<SPAN class=br0>(</SPAN>matrix<SPAN class=br0>)</SPAN>
  <SPAN class=kw1>while</SPAN> <SPAN class=kw2>true</SPAN>
    options = <SPAN class=br0>[</SPAN><SPAN class=br0>]</SPAN>
    <SPAN class=br0>(</SPAN>0..8<SPAN class=br0>)</SPAN>.<SPAN class=me1>each</SPAN> <SPAN class=br0>{</SPAN> <SPAN class=sy0>|</SPAN>i<SPAN class=sy0>|</SPAN>
      <SPAN class=br0>(</SPAN>0..8<SPAN class=br0>)</SPAN>.<SPAN class=me1>each</SPAN> <SPAN class=br0>{</SPAN> <SPAN class=sy0>|</SPAN>j<SPAN class=sy0>|</SPAN>
        <SPAN class=kw1>next</SPAN> <SPAN class=kw1>if</SPAN> matrix<SPAN class=br0>[</SPAN>i<SPAN class=br0>]</SPAN><SPAN class=br0>[</SPAN>j<SPAN class=br0>]</SPAN> != 0
        <SPAN class=kw3>p</SPAN> = permissible<SPAN class=br0>(</SPAN>matrix, i, j<SPAN class=br0>)</SPAN>
        <SPAN class=co1># If nothing is permissible, there is no solution at this level.</SPAN>
        <SPAN class=kw2>return</SPAN> <SPAN class=kw2>false</SPAN> <SPAN class=kw1>if</SPAN> <SPAN class=br0>(</SPAN><SPAN class=kw3>p</SPAN>.<SPAN class=me1>length</SPAN> == 0<SPAN class=br0>)</SPAN>
        options.<SPAN class=me1>push</SPAN><SPAN class=br0>(</SPAN><SPAN class=br0>{</SPAN>:i <SPAN class=sy0>=&gt;</SPAN> i, <SPAN class=re3>:j</SPAN> <SPAN class=sy0>=&gt;</SPAN> j, <SPAN class=re3>:permissible</SPAN> <SPAN class=sy0>=&gt;</SPAN> <SPAN class=kw3>p</SPAN><SPAN class=br0>}</SPAN><SPAN class=br0>)</SPAN>
      <SPAN class=br0>}</SPAN>
    <SPAN class=br0>}</SPAN>
    <SPAN class=co1># If the matrix is complete, we have a solution...</SPAN>
    <SPAN class=kw2>return</SPAN> matrix <SPAN class=kw1>if</SPAN> options.<SPAN class=me1>length</SPAN> == 0
 
    omin = options.<SPAN class=me1>min</SPAN> <SPAN class=br0>{</SPAN> <SPAN class=sy0>|</SPAN> a, b <SPAN class=sy0>|</SPAN>
      a<SPAN class=br0>[</SPAN><SPAN class=re3>:permissible</SPAN><SPAN class=br0>]</SPAN>.<SPAN class=me1>length</SPAN> <SPAN class=sy0>&lt;=&gt;</SPAN> b<SPAN class=br0>[</SPAN><SPAN class=re3>:permissible</SPAN><SPAN class=br0>]</SPAN>.<SPAN class=me1>length</SPAN>
    <SPAN class=br0>}</SPAN>
 
    <SPAN class=co1># If there is an option with only one solution, set it and re-check permissibility</SPAN>
    <SPAN class=kw1>if</SPAN> omin<SPAN class=br0>[</SPAN><SPAN class=re3>:permissible</SPAN><SPAN class=br0>]</SPAN>.<SPAN class=me1>length</SPAN> == 1
      matrix<SPAN class=br0>[</SPAN>omin<SPAN class=br0>[</SPAN><SPAN class=re3>:i</SPAN><SPAN class=br0>]</SPAN><SPAN class=br0>]</SPAN><SPAN class=br0>[</SPAN>omin<SPAN class=br0>[</SPAN><SPAN class=re3>:j</SPAN><SPAN class=br0>]</SPAN><SPAN class=br0>]</SPAN> = omin<SPAN class=br0>[</SPAN><SPAN class=re3>:permissible</SPAN><SPAN class=br0>]</SPAN><SPAN class=br0>[</SPAN>0<SPAN class=br0>]</SPAN>
      <SPAN class=kw1>next</SPAN>
    <SPAN class=kw1>end</SPAN>
 
    <SPAN class=co1># We have two or more choices. We need to search both...</SPAN>
    omin<SPAN class=br0>[</SPAN><SPAN class=re3>:permissible</SPAN><SPAN class=br0>]</SPAN>.<SPAN class=me1>each</SPAN> <SPAN class=br0>{</SPAN> <SPAN class=sy0>|</SPAN>v<SPAN class=sy0>|</SPAN>
      mtmp = deep_copy_sudoku<SPAN class=br0>(</SPAN>matrix<SPAN class=br0>)</SPAN>
      mtmp<SPAN class=br0>[</SPAN>omin<SPAN class=br0>[</SPAN><SPAN class=re3>:i</SPAN><SPAN class=br0>]</SPAN><SPAN class=br0>]</SPAN><SPAN class=br0>[</SPAN>omin<SPAN class=br0>[</SPAN><SPAN class=re3>:j</SPAN><SPAN class=br0>]</SPAN><SPAN class=br0>]</SPAN> = v
      ret = solve_sudoku<SPAN class=br0>(</SPAN>mtmp<SPAN class=br0>)</SPAN>
      <SPAN class=kw1>if</SPAN> ret != <SPAN class=kw2>false</SPAN>
        <SPAN class=kw2>return</SPAN> ret
      <SPAN class=kw1>end</SPAN>
    <SPAN class=br0>}</SPAN>
 
    <SPAN class=co1># We did an exhaustive search on this branch and nothing worked out.</SPAN>
    <SPAN class=kw2>return</SPAN> <SPAN class=kw2>false</SPAN>
  <SPAN class=kw1>end</SPAN>
<SPAN class=kw1>end</SPAN>
 
<SPAN class=kw1>def</SPAN> print_matrix<SPAN class=br0>(</SPAN>matrix<SPAN class=br0>)</SPAN>
  <SPAN class=kw1>if</SPAN> <SPAN class=br0>(</SPAN>matrix == <SPAN class=kw2>false</SPAN><SPAN class=br0>)</SPAN>
    <SPAN class=kw3>print</SPAN> <SPAN class=st0>"Impossible<SPAN class=es0>\n</SPAN>"</SPAN>
    <SPAN class=kw2>return</SPAN>
  <SPAN class=kw1>end</SPAN>
 
  <SPAN class=br0>(</SPAN>0..8<SPAN class=br0>)</SPAN>.<SPAN class=me1>each</SPAN> <SPAN class=br0>{</SPAN> <SPAN class=sy0>|</SPAN>i<SPAN class=sy0>|</SPAN>
    <SPAN class=br0>(</SPAN>0..8<SPAN class=br0>)</SPAN>.<SPAN class=me1>each</SPAN> <SPAN class=br0>{</SPAN> <SPAN class=sy0>|</SPAN>j<SPAN class=sy0>|</SPAN>
      <SPAN class=kw3>print</SPAN> matrix<SPAN class=br0>[</SPAN>i<SPAN class=br0>]</SPAN><SPAN class=br0>[</SPAN>j<SPAN class=br0>]</SPAN>
    <SPAN class=br0>}</SPAN>
    <SPAN class=kw3>print</SPAN> <SPAN class=st0>"<SPAN class=es0>\n</SPAN>"</SPAN>
  <SPAN class=br0>}</SPAN>
<SPAN class=kw1>end</SPAN>
 
print_matrix<SPAN class=br0>(</SPAN>solve_sudoku<SPAN class=br0>(</SPAN>read_matrix<SPAN class=br0>(</SPAN><SPAN class=br0>)</SPAN><SPAN class=br0>)</SPAN><SPAN class=br0>)</SPAN>
</PRE></DIV></DIV>
<H3><SPAN class=editsection>[<A 
title="Edit section: Example of a brute force Sudoku solver (in C)" 
href="http://en.wikipedia.org/w/index.php?title=Algorithmics_of_sudoku&amp;action=edit&amp;section=12">edit</A>]</SPAN> 
<SPAN class=mw-headline 
id=Example_of_a_brute_force_Sudoku_solver_.28in_C.29>Example of a brute force 
Sudoku solver (in C)</SPAN></H3>
<DIV class=mw-geshi dir=ltr style="TEXT-ALIGN: left">
<DIV class="c source-c" style="FONT-FAMILY: monospace"><PRE class=de1><SPAN class=co2>#include &lt;stdio.h&gt;</SPAN>
 
<SPAN class=kw4>int</SPAN> grid<SPAN class=br0>[</SPAN>9<SPAN class=br0>]</SPAN><SPAN class=br0>[</SPAN>9<SPAN class=br0>]</SPAN><SPAN class=sy0>;</SPAN>
 
<SPAN class=kw4>void</SPAN> print_solution<SPAN class=br0>(</SPAN><SPAN class=kw4>void</SPAN><SPAN class=br0>)</SPAN>
<SPAN class=br0>{</SPAN>
  <SPAN class=kw4>static</SPAN> <SPAN class=kw4>int</SPAN> nsol <SPAN class=sy0>=</SPAN> <SPAN class=nu0>0</SPAN><SPAN class=sy0>;</SPAN>
  <SPAN class=kw4>int</SPAN> r<SPAN class=sy0>,</SPAN> c<SPAN class=sy0>;</SPAN>
  <SPAN class=kw3>printf</SPAN><SPAN class=br0>(</SPAN><SPAN class=st0>"----- solution %d -----<SPAN class=es1>\n</SPAN>"</SPAN><SPAN class=sy0>,</SPAN> <SPAN class=sy0>++</SPAN>nsol<SPAN class=br0>)</SPAN><SPAN class=sy0>;</SPAN>
  <SPAN class=kw1>for</SPAN> <SPAN class=br0>(</SPAN>r <SPAN class=sy0>=</SPAN> <SPAN class=nu0>0</SPAN><SPAN class=sy0>;</SPAN> r <SPAN class=sy0>&lt;</SPAN> <SPAN class=nu0>9</SPAN><SPAN class=sy0>;</SPAN> r<SPAN class=sy0>++</SPAN><SPAN class=br0>)</SPAN>
  <SPAN class=br0>{</SPAN>
    <SPAN class=kw1>for</SPAN> <SPAN class=br0>(</SPAN>c <SPAN class=sy0>=</SPAN> <SPAN class=nu0>0</SPAN><SPAN class=sy0>;</SPAN> c <SPAN class=sy0>&lt;</SPAN> <SPAN class=nu0>9</SPAN><SPAN class=sy0>;</SPAN> c<SPAN class=sy0>++</SPAN><SPAN class=br0>)</SPAN>
    <SPAN class=br0>{</SPAN>
      <SPAN class=kw3>printf</SPAN><SPAN class=br0>(</SPAN><SPAN class=st0>"%d"</SPAN><SPAN class=sy0>,</SPAN> grid<SPAN class=br0>[</SPAN>r<SPAN class=br0>]</SPAN><SPAN class=br0>[</SPAN>c<SPAN class=br0>]</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>;</SPAN>
      <SPAN class=kw1>if</SPAN> <SPAN class=br0>(</SPAN>c <SPAN class=sy0>%</SPAN> 3 <SPAN class=sy0>==</SPAN> 2<SPAN class=br0>)</SPAN> <SPAN class=kw3>printf</SPAN><SPAN class=br0>(</SPAN><SPAN class=st0>"  "</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>;</SPAN>
    <SPAN class=br0>}</SPAN>
    <SPAN class=kw3>printf</SPAN><SPAN class=br0>(</SPAN><SPAN class=st0>"<SPAN class=es1>\n</SPAN>"</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>;</SPAN>
    <SPAN class=kw1>if</SPAN> <SPAN class=br0>(</SPAN>r <SPAN class=sy0>%</SPAN> 3 <SPAN class=sy0>==</SPAN> 2<SPAN class=br0>)</SPAN> <SPAN class=kw3>printf</SPAN><SPAN class=br0>(</SPAN><SPAN class=st0>"<SPAN class=es1>\n</SPAN>"</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>;</SPAN>
  <SPAN class=br0>}</SPAN>
<SPAN class=br0>}</SPAN>
 
<SPAN class=kw4>int</SPAN> safe<SPAN class=br0>(</SPAN><SPAN class=kw4>int</SPAN> row<SPAN class=sy0>,</SPAN> <SPAN class=kw4>int</SPAN> col<SPAN class=sy0>,</SPAN> <SPAN class=kw4>int</SPAN> n<SPAN class=br0>)</SPAN>
<SPAN class=br0>{</SPAN>
  <SPAN class=kw4>int</SPAN> r<SPAN class=sy0>,</SPAN> c<SPAN class=sy0>,</SPAN> br<SPAN class=sy0>,</SPAN> bc<SPAN class=sy0>;</SPAN>
 
  <SPAN class=kw1>if</SPAN> <SPAN class=br0>(</SPAN>grid<SPAN class=br0>[</SPAN>row<SPAN class=br0>]</SPAN><SPAN class=br0>[</SPAN>col<SPAN class=br0>]</SPAN> <SPAN class=sy0>==</SPAN> n<SPAN class=br0>)</SPAN> <SPAN class=kw1>return</SPAN> <SPAN class=nu0>1</SPAN><SPAN class=sy0>;</SPAN>
  <SPAN class=kw1>if</SPAN> <SPAN class=br0>(</SPAN>grid<SPAN class=br0>[</SPAN>row<SPAN class=br0>]</SPAN><SPAN class=br0>[</SPAN>col<SPAN class=br0>]</SPAN> <SPAN class=sy0>!=</SPAN> 0<SPAN class=br0>)</SPAN> <SPAN class=kw1>return</SPAN> <SPAN class=nu0>0</SPAN><SPAN class=sy0>;</SPAN>
  <SPAN class=kw1>for</SPAN> <SPAN class=br0>(</SPAN>c <SPAN class=sy0>=</SPAN> <SPAN class=nu0>0</SPAN><SPAN class=sy0>;</SPAN> c <SPAN class=sy0>&lt;</SPAN> <SPAN class=nu0>9</SPAN><SPAN class=sy0>;</SPAN> c<SPAN class=sy0>++</SPAN><SPAN class=br0>)</SPAN>
    <SPAN class=kw1>if</SPAN> <SPAN class=br0>(</SPAN>grid<SPAN class=br0>[</SPAN>row<SPAN class=br0>]</SPAN><SPAN class=br0>[</SPAN>c<SPAN class=br0>]</SPAN> <SPAN class=sy0>==</SPAN> n<SPAN class=br0>)</SPAN> <SPAN class=kw1>return</SPAN> <SPAN class=nu0>0</SPAN><SPAN class=sy0>;</SPAN>
  <SPAN class=kw1>for</SPAN> <SPAN class=br0>(</SPAN>r <SPAN class=sy0>=</SPAN> <SPAN class=nu0>0</SPAN><SPAN class=sy0>;</SPAN> r <SPAN class=sy0>&lt;</SPAN> <SPAN class=nu0>9</SPAN><SPAN class=sy0>;</SPAN> r<SPAN class=sy0>++</SPAN><SPAN class=br0>)</SPAN>
    <SPAN class=kw1>if</SPAN> <SPAN class=br0>(</SPAN>grid<SPAN class=br0>[</SPAN>r<SPAN class=br0>]</SPAN><SPAN class=br0>[</SPAN>col<SPAN class=br0>]</SPAN> <SPAN class=sy0>==</SPAN> n<SPAN class=br0>)</SPAN> <SPAN class=kw1>return</SPAN> <SPAN class=nu0>0</SPAN><SPAN class=sy0>;</SPAN>
  br <SPAN class=sy0>=</SPAN> row <SPAN class=sy0>/</SPAN> <SPAN class=nu0>3</SPAN><SPAN class=sy0>;</SPAN>
  bc <SPAN class=sy0>=</SPAN> col <SPAN class=sy0>/</SPAN> <SPAN class=nu0>3</SPAN><SPAN class=sy0>;</SPAN>
  <SPAN class=kw1>for</SPAN> <SPAN class=br0>(</SPAN>r <SPAN class=sy0>=</SPAN> br <SPAN class=sy0>*</SPAN> <SPAN class=nu0>3</SPAN><SPAN class=sy0>;</SPAN> r <SPAN class=sy0>&lt;</SPAN> <SPAN class=br0>(</SPAN>br <SPAN class=sy0>+</SPAN> 1<SPAN class=br0>)</SPAN> <SPAN class=sy0>*</SPAN> <SPAN class=nu0>3</SPAN><SPAN class=sy0>;</SPAN> r<SPAN class=sy0>++</SPAN><SPAN class=br0>)</SPAN>
    <SPAN class=kw1>for</SPAN> <SPAN class=br0>(</SPAN>c <SPAN class=sy0>=</SPAN> bc <SPAN class=sy0>*</SPAN> <SPAN class=nu0>3</SPAN><SPAN class=sy0>;</SPAN> c <SPAN class=sy0>&lt;</SPAN> <SPAN class=br0>(</SPAN>bc <SPAN class=sy0>+</SPAN> 1<SPAN class=br0>)</SPAN> <SPAN class=sy0>*</SPAN> <SPAN class=nu0>3</SPAN><SPAN class=sy0>;</SPAN> c<SPAN class=sy0>++</SPAN><SPAN class=br0>)</SPAN>
      <SPAN class=kw1>if</SPAN> <SPAN class=br0>(</SPAN>grid<SPAN class=br0>[</SPAN>r<SPAN class=br0>]</SPAN><SPAN class=br0>[</SPAN>c<SPAN class=br0>]</SPAN> <SPAN class=sy0>==</SPAN> n<SPAN class=br0>)</SPAN> <SPAN class=kw1>return</SPAN> <SPAN class=nu0>0</SPAN><SPAN class=sy0>;</SPAN>
 
  <SPAN class=kw1>return</SPAN> <SPAN class=nu0>1</SPAN><SPAN class=sy0>;</SPAN>
<SPAN class=br0>}</SPAN>
 
<SPAN class=kw4>void</SPAN> solve<SPAN class=br0>(</SPAN><SPAN class=kw4>int</SPAN> row<SPAN class=sy0>,</SPAN> <SPAN class=kw4>int</SPAN> col<SPAN class=br0>)</SPAN>
<SPAN class=br0>{</SPAN>
  <SPAN class=kw4>int</SPAN> n<SPAN class=sy0>,</SPAN> t<SPAN class=sy0>;</SPAN>
 
  <SPAN class=kw1>if</SPAN> <SPAN class=br0>(</SPAN>row <SPAN class=sy0>==</SPAN> 9<SPAN class=br0>)</SPAN>
    print_solution<SPAN class=br0>(</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>;</SPAN>
  <SPAN class=kw1>else</SPAN>
    <SPAN class=kw1>for</SPAN> <SPAN class=br0>(</SPAN>n <SPAN class=sy0>=</SPAN> <SPAN class=nu0>1</SPAN><SPAN class=sy0>;</SPAN> n <SPAN class=sy0>&lt;=</SPAN> <SPAN class=nu0>9</SPAN><SPAN class=sy0>;</SPAN> n<SPAN class=sy0>++</SPAN><SPAN class=br0>)</SPAN>
      <SPAN class=kw1>if</SPAN> <SPAN class=br0>(</SPAN>safe<SPAN class=br0>(</SPAN>row<SPAN class=sy0>,</SPAN> col<SPAN class=sy0>,</SPAN> n<SPAN class=br0>)</SPAN><SPAN class=br0>)</SPAN> <SPAN class=br0>{</SPAN>
	t <SPAN class=sy0>=</SPAN> grid<SPAN class=br0>[</SPAN>row<SPAN class=br0>]</SPAN><SPAN class=br0>[</SPAN>col<SPAN class=br0>]</SPAN><SPAN class=sy0>;</SPAN>
	grid<SPAN class=br0>[</SPAN>row<SPAN class=br0>]</SPAN><SPAN class=br0>[</SPAN>col<SPAN class=br0>]</SPAN> <SPAN class=sy0>=</SPAN> n<SPAN class=sy0>;</SPAN>
	<SPAN class=kw1>if</SPAN> <SPAN class=br0>(</SPAN>col <SPAN class=sy0>==</SPAN> 8<SPAN class=br0>)</SPAN>
	  solve<SPAN class=br0>(</SPAN>row <SPAN class=sy0>+</SPAN> 1<SPAN class=sy0>,</SPAN> 0<SPAN class=br0>)</SPAN><SPAN class=sy0>;</SPAN>
	<SPAN class=kw1>else</SPAN>
	  solve<SPAN class=br0>(</SPAN>row<SPAN class=sy0>,</SPAN> col <SPAN class=sy0>+</SPAN> 1<SPAN class=br0>)</SPAN><SPAN class=sy0>;</SPAN>
 
	grid<SPAN class=br0>[</SPAN>row<SPAN class=br0>]</SPAN><SPAN class=br0>[</SPAN>col<SPAN class=br0>]</SPAN> <SPAN class=sy0>=</SPAN> t<SPAN class=sy0>;</SPAN>
      <SPAN class=br0>}</SPAN>
<SPAN class=br0>}</SPAN>
 
<SPAN class=kw4>int</SPAN>
main<SPAN class=br0>(</SPAN><SPAN class=br0>)</SPAN>
<SPAN class=br0>{</SPAN>
  <SPAN class=kw4>int</SPAN> i<SPAN class=sy0>,</SPAN> j<SPAN class=sy0>;</SPAN>
 
  <SPAN class=kw3>printf</SPAN><SPAN class=br0>(</SPAN><SPAN class=st0>"enter the sudoku: <SPAN class=es1>\n</SPAN>"</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>;</SPAN>
  <SPAN class=kw1>for</SPAN><SPAN class=br0>(</SPAN>i<SPAN class=sy0>=</SPAN><SPAN class=nu0>0</SPAN><SPAN class=sy0>;</SPAN>i<SPAN class=sy0>&lt;</SPAN><SPAN class=nu0>9</SPAN><SPAN class=sy0>;</SPAN>i<SPAN class=sy0>++</SPAN><SPAN class=br0>)</SPAN>
    <SPAN class=kw1>for</SPAN><SPAN class=br0>(</SPAN>j<SPAN class=sy0>=</SPAN><SPAN class=nu0>0</SPAN><SPAN class=sy0>;</SPAN>j<SPAN class=sy0>&lt;</SPAN><SPAN class=nu0>9</SPAN><SPAN class=sy0>;</SPAN>j<SPAN class=sy0>++</SPAN><SPAN class=br0>)</SPAN>
    <SPAN class=br0>{</SPAN>
      <SPAN class=kw3>printf</SPAN><SPAN class=br0>(</SPAN><SPAN class=st0>"(%d, %d): "</SPAN><SPAN class=sy0>,</SPAN> i<SPAN class=sy0>+</SPAN>1<SPAN class=sy0>,</SPAN> j<SPAN class=sy0>+</SPAN>1<SPAN class=br0>)</SPAN><SPAN class=sy0>;</SPAN>
      scanf<SPAN class=br0>(</SPAN><SPAN class=st0>"%d"</SPAN><SPAN class=sy0>,</SPAN> <SPAN class=sy0>&amp;</SPAN>grid<SPAN class=br0>[</SPAN>i<SPAN class=br0>]</SPAN><SPAN class=br0>[</SPAN>j<SPAN class=br0>]</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>;</SPAN>
    <SPAN class=br0>}</SPAN>
  solve<SPAN class=br0>(</SPAN>0<SPAN class=sy0>,</SPAN>0<SPAN class=br0>)</SPAN><SPAN class=sy0>;</SPAN>
  <SPAN class=kw1>return</SPAN> <SPAN class=nu0>0</SPAN><SPAN class=sy0>;</SPAN>
<SPAN class=br0>}</SPAN>
</PRE></DIV></DIV>
<H3><SPAN class=editsection>[<A 
title="Edit section: Example of Sudoku solver (in Prolog)" 
href="http://en.wikipedia.org/w/index.php?title=Algorithmics_of_sudoku&amp;action=edit&amp;section=13">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Example_of_Sudoku_solver_.28in_Prolog.29>Example of 
Sudoku solver (in Prolog)</SPAN></H3>
<P>Using C syntax highlighting</P>
<DIV class=mw-geshi dir=ltr style="TEXT-ALIGN: left">
<DIV class="c source-c" style="FONT-FAMILY: monospace"><PRE class=de1><SPAN class=coMULTI>/** Helper relation, more readable than member() */</SPAN>
<SPAN class=sy0>:-</SPAN>op<SPAN class=br0>(</SPAN><SPAN class=nu0>400</SPAN><SPAN class=sy0>,</SPAN> xfx<SPAN class=sy0>,</SPAN> in<SPAN class=br0>)</SPAN>.
<SPAN class=me1>X</SPAN> in L <SPAN class=sy0>:-</SPAN> member<SPAN class=br0>(</SPAN>X<SPAN class=sy0>,</SPAN> L<SPAN class=br0>)</SPAN>.
 
<SPAN class=coMULTI>/**
* The standard sudoku relation is defined by following predicate:
*   - R -- row number
*   - C -- column number
*   - A -- 3x3 area number
*/</SPAN>
related<SPAN class=br0>(</SPAN>vt<SPAN class=br0>(</SPAN>R<SPAN class=sy0>,</SPAN>_<SPAN class=sy0>,</SPAN>_<SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN> vt<SPAN class=br0>(</SPAN>R<SPAN class=sy0>,</SPAN>_<SPAN class=sy0>,</SPAN>_<SPAN class=br0>)</SPAN><SPAN class=br0>)</SPAN>.
<SPAN class=me1>related</SPAN><SPAN class=br0>(</SPAN>vt<SPAN class=br0>(</SPAN>_<SPAN class=sy0>,</SPAN>C<SPAN class=sy0>,</SPAN>_<SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN> vt<SPAN class=br0>(</SPAN>_<SPAN class=sy0>,</SPAN>C<SPAN class=sy0>,</SPAN>_<SPAN class=br0>)</SPAN><SPAN class=br0>)</SPAN>.
<SPAN class=me1>related</SPAN><SPAN class=br0>(</SPAN>vt<SPAN class=br0>(</SPAN>_<SPAN class=sy0>,</SPAN>_<SPAN class=sy0>,</SPAN>A<SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN> vt<SPAN class=br0>(</SPAN>_<SPAN class=sy0>,</SPAN>_<SPAN class=sy0>,</SPAN>A<SPAN class=br0>)</SPAN><SPAN class=br0>)</SPAN>.
 
<SPAN class=coMULTI>/**
* Brute force sudoku solver (graph colouring).
*
* For all vertices(1) choose a color from Colors, such
* that none of the related vertices have the same color.
* Grouping constraints are encoded in releatd(V1, V2) predicate.
*/</SPAN>
sudoku_solve<SPAN class=br0>(</SPAN><SPAN class=br0>[</SPAN><SPAN class=br0>]</SPAN><SPAN class=sy0>,</SPAN> _<SPAN class=sy0>,</SPAN> _<SPAN class=sy0>,</SPAN> Solution<SPAN class=sy0>,</SPAN> Solution<SPAN class=br0>)</SPAN>.
<SPAN class=me1>sudoku_solve</SPAN><SPAN class=br0>(</SPAN><SPAN class=br0>[</SPAN>V <SPAN class=sy0>|</SPAN> Vr<SPAN class=br0>]</SPAN><SPAN class=sy0>,</SPAN> Colors<SPAN class=sy0>,</SPAN> Hints<SPAN class=sy0>,</SPAN> Solution<SPAN class=sy0>,</SPAN> Result<SPAN class=br0>)</SPAN> <SPAN class=sy0>:-</SPAN>
    s<SPAN class=br0>(</SPAN>V<SPAN class=sy0>,</SPAN>Ch<SPAN class=br0>)</SPAN> in Hints <SPAN class=sy0>-&gt;</SPAN> <SPAN class=sy0>%</SPAN> already given as hint
        sudoku_solve<SPAN class=br0>(</SPAN>Vr<SPAN class=sy0>,</SPAN> Colors<SPAN class=sy0>,</SPAN> Hints<SPAN class=sy0>,</SPAN> <SPAN class=br0>[</SPAN>s<SPAN class=br0>(</SPAN>V<SPAN class=sy0>,</SPAN>Ch<SPAN class=br0>)</SPAN> <SPAN class=sy0>|</SPAN> Solution<SPAN class=br0>]</SPAN><SPAN class=sy0>,</SPAN> Result<SPAN class=br0>)</SPAN>
    <SPAN class=sy0>;</SPAN> <SPAN class=br0>(</SPAN>
        C in Colors<SPAN class=sy0>,</SPAN> <SPAN class=sy0>%</SPAN>try next color
        forall<SPAN class=br0>(</SPAN>s<SPAN class=br0>(</SPAN>Vs1<SPAN class=sy0>,</SPAN>Cs1<SPAN class=br0>)</SPAN> in Hints<SPAN class=sy0>,</SPAN> <SPAN class=br0>(</SPAN>Cs1 \<SPAN class=sy0>=</SPAN> C <SPAN class=sy0>;</SPAN> not<SPAN class=br0>(</SPAN>related<SPAN class=br0>(</SPAN>V<SPAN class=sy0>,</SPAN> Vs1<SPAN class=br0>)</SPAN><SPAN class=br0>)</SPAN><SPAN class=br0>)</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN> <SPAN class=sy0>%</SPAN> hints reserved
        forall<SPAN class=br0>(</SPAN>s<SPAN class=br0>(</SPAN>Vs2<SPAN class=sy0>,</SPAN>Cs2<SPAN class=br0>)</SPAN> in Solution<SPAN class=sy0>,</SPAN> <SPAN class=br0>(</SPAN>Cs2 \<SPAN class=sy0>=</SPAN> C <SPAN class=sy0>;</SPAN> not<SPAN class=br0>(</SPAN>related<SPAN class=br0>(</SPAN>V<SPAN class=sy0>,</SPAN> Vs2<SPAN class=br0>)</SPAN><SPAN class=br0>)</SPAN><SPAN class=br0>)</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN> <SPAN class=sy0>%</SPAN> ensure color is unique
        sudoku_solve<SPAN class=br0>(</SPAN>Vr<SPAN class=sy0>,</SPAN> Colors<SPAN class=sy0>,</SPAN> Hints<SPAN class=sy0>,</SPAN> <SPAN class=br0>[</SPAN>s<SPAN class=br0>(</SPAN>V<SPAN class=sy0>,</SPAN>C<SPAN class=br0>)</SPAN> <SPAN class=sy0>|</SPAN> Solution<SPAN class=br0>]</SPAN><SPAN class=sy0>,</SPAN> Result<SPAN class=br0>)</SPAN> <SPAN class=sy0>%</SPAN>repeat <SPAN class=kw1>for</SPAN> the rest
    <SPAN class=br0>)</SPAN>.
 
<SPAN class=sy0>%</SPAN> <SPAN class=sy0>======-</SPAN> End of program. <SPAN class=me1>The</SPAN> following is the test of code above <SPAN class=sy0>-===========</SPAN>
<SPAN class=sy0>%</SPAN> define colors
colors<SPAN class=br0>(</SPAN>C<SPAN class=br0>)</SPAN> <SPAN class=sy0>:-</SPAN> C <SPAN class=sy0>=</SPAN> <SPAN class=br0>[</SPAN>1<SPAN class=sy0>,</SPAN> 2<SPAN class=sy0>,</SPAN> 3<SPAN class=sy0>,</SPAN> 4<SPAN class=sy0>,</SPAN> 5<SPAN class=sy0>,</SPAN> 6<SPAN class=sy0>,</SPAN> 7<SPAN class=sy0>,</SPAN> 8<SPAN class=sy0>,</SPAN> 9<SPAN class=br0>]</SPAN>.
 
<SPAN class=sy0>%</SPAN> define board
test_board<SPAN class=br0>(</SPAN>B<SPAN class=br0>)</SPAN> <SPAN class=sy0>:-</SPAN> 
    colors<SPAN class=br0>(</SPAN>C<SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN>
    def_row_board<SPAN class=br0>(</SPAN>C<SPAN class=sy0>,</SPAN> C<SPAN class=sy0>,</SPAN> <SPAN class=br0>[</SPAN><SPAN class=br0>]</SPAN><SPAN class=sy0>,</SPAN> B<SPAN class=br0>)</SPAN>.
 
<SPAN class=me1>def_row_board</SPAN><SPAN class=br0>(</SPAN><SPAN class=br0>[</SPAN><SPAN class=br0>]</SPAN><SPAN class=sy0>,</SPAN> _<SPAN class=sy0>,</SPAN> S<SPAN class=sy0>,</SPAN> S<SPAN class=br0>)</SPAN>.
<SPAN class=me1>def_row_board</SPAN><SPAN class=br0>(</SPAN><SPAN class=br0>[</SPAN>R <SPAN class=sy0>|</SPAN> Rs<SPAN class=br0>]</SPAN><SPAN class=sy0>,</SPAN> C<SPAN class=sy0>,</SPAN> B<SPAN class=sy0>,</SPAN> S<SPAN class=br0>)</SPAN> <SPAN class=sy0>:-</SPAN>
    def_col_board<SPAN class=br0>(</SPAN>R<SPAN class=sy0>,</SPAN> C<SPAN class=sy0>,</SPAN> B<SPAN class=sy0>,</SPAN> S1<SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN>
    def_row_board<SPAN class=br0>(</SPAN>Rs<SPAN class=sy0>,</SPAN> C<SPAN class=sy0>,</SPAN> S1<SPAN class=sy0>,</SPAN> S<SPAN class=br0>)</SPAN>.
 
<SPAN class=me1>def_col_board</SPAN><SPAN class=br0>(</SPAN>_<SPAN class=sy0>,</SPAN> <SPAN class=br0>[</SPAN><SPAN class=br0>]</SPAN><SPAN class=sy0>,</SPAN> S<SPAN class=sy0>,</SPAN> S<SPAN class=br0>)</SPAN>.
<SPAN class=me1>def_col_board</SPAN><SPAN class=br0>(</SPAN>R<SPAN class=sy0>,</SPAN> <SPAN class=br0>[</SPAN>C <SPAN class=sy0>|</SPAN> Cs<SPAN class=br0>]</SPAN><SPAN class=sy0>,</SPAN> B<SPAN class=sy0>,</SPAN> S<SPAN class=br0>)</SPAN> <SPAN class=sy0>:-</SPAN>
    K is <SPAN class=br0>(</SPAN><SPAN class=br0>(</SPAN>R <SPAN class=sy0>-</SPAN> <SPAN class=nu0>1</SPAN><SPAN class=br0>)</SPAN> <SPAN class=co1>// 3) * 3,</SPAN>
    J is <SPAN class=br0>(</SPAN><SPAN class=br0>(</SPAN>C <SPAN class=sy0>-</SPAN> <SPAN class=nu0>1</SPAN><SPAN class=br0>)</SPAN> <SPAN class=co1>// 3) + 1,</SPAN>
    A is K <SPAN class=sy0>+</SPAN> J<SPAN class=sy0>,</SPAN>
    def_col_board<SPAN class=br0>(</SPAN>R<SPAN class=sy0>,</SPAN> Cs<SPAN class=sy0>,</SPAN> <SPAN class=br0>[</SPAN>vt<SPAN class=br0>(</SPAN>R<SPAN class=sy0>,</SPAN> C<SPAN class=sy0>,</SPAN> A<SPAN class=br0>)</SPAN> <SPAN class=sy0>|</SPAN> B<SPAN class=br0>]</SPAN><SPAN class=sy0>,</SPAN> S<SPAN class=br0>)</SPAN>.
 
<SPAN class=sy0>%</SPAN> hints from image example above
hints<SPAN class=br0>(</SPAN>H<SPAN class=br0>)</SPAN> <SPAN class=sy0>:-</SPAN> H <SPAN class=sy0>=</SPAN> <SPAN class=br0>[</SPAN>s<SPAN class=br0>(</SPAN>vt<SPAN class=br0>(</SPAN><SPAN class=nu0>1</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>1</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>1</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN> <SPAN class=nu0>5</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN>
    s<SPAN class=br0>(</SPAN>vt<SPAN class=br0>(</SPAN><SPAN class=nu0>1</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>2</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>1</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN> <SPAN class=nu0>3</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN>
    s<SPAN class=br0>(</SPAN>vt<SPAN class=br0>(</SPAN><SPAN class=nu0>1</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>5</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>2</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN> <SPAN class=nu0>7</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN>
    s<SPAN class=br0>(</SPAN>vt<SPAN class=br0>(</SPAN><SPAN class=nu0>2</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>1</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>1</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN> <SPAN class=nu0>6</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN>
    s<SPAN class=br0>(</SPAN>vt<SPAN class=br0>(</SPAN><SPAN class=nu0>2</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>4</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>2</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN> <SPAN class=nu0>1</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN>
    s<SPAN class=br0>(</SPAN>vt<SPAN class=br0>(</SPAN><SPAN class=nu0>2</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>5</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>2</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN> <SPAN class=nu0>9</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN>
    s<SPAN class=br0>(</SPAN>vt<SPAN class=br0>(</SPAN><SPAN class=nu0>2</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>6</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>2</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN> <SPAN class=nu0>5</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN>
    s<SPAN class=br0>(</SPAN>vt<SPAN class=br0>(</SPAN><SPAN class=nu0>3</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>2</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>1</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN> <SPAN class=nu0>9</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN>
    s<SPAN class=br0>(</SPAN>vt<SPAN class=br0>(</SPAN><SPAN class=nu0>3</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>3</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>1</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN> <SPAN class=nu0>8</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN>
    s<SPAN class=br0>(</SPAN>vt<SPAN class=br0>(</SPAN><SPAN class=nu0>3</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>8</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>3</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN> <SPAN class=nu0>6</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN>
    s<SPAN class=br0>(</SPAN>vt<SPAN class=br0>(</SPAN><SPAN class=nu0>4</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>1</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>4</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN> <SPAN class=nu0>8</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN>
    s<SPAN class=br0>(</SPAN>vt<SPAN class=br0>(</SPAN><SPAN class=nu0>4</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>5</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>5</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN> <SPAN class=nu0>6</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN>
    s<SPAN class=br0>(</SPAN>vt<SPAN class=br0>(</SPAN><SPAN class=nu0>4</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>9</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>6</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN> <SPAN class=nu0>3</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN>
    s<SPAN class=br0>(</SPAN>vt<SPAN class=br0>(</SPAN><SPAN class=nu0>5</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>1</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>4</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN> <SPAN class=nu0>4</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN>
    s<SPAN class=br0>(</SPAN>vt<SPAN class=br0>(</SPAN><SPAN class=nu0>5</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>4</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>5</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN> <SPAN class=nu0>8</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN>
    s<SPAN class=br0>(</SPAN>vt<SPAN class=br0>(</SPAN><SPAN class=nu0>5</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>6</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>5</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN> <SPAN class=nu0>3</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN>
    s<SPAN class=br0>(</SPAN>vt<SPAN class=br0>(</SPAN><SPAN class=nu0>5</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>9</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>6</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN> <SPAN class=nu0>1</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN>
    s<SPAN class=br0>(</SPAN>vt<SPAN class=br0>(</SPAN><SPAN class=nu0>6</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>1</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>4</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN> <SPAN class=nu0>7</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN>
    s<SPAN class=br0>(</SPAN>vt<SPAN class=br0>(</SPAN><SPAN class=nu0>6</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>5</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>5</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN> <SPAN class=nu0>2</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN>
    s<SPAN class=br0>(</SPAN>vt<SPAN class=br0>(</SPAN><SPAN class=nu0>6</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>9</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>6</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN> <SPAN class=nu0>6</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN>
    s<SPAN class=br0>(</SPAN>vt<SPAN class=br0>(</SPAN><SPAN class=nu0>7</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>2</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>7</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN> <SPAN class=nu0>6</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN>
    s<SPAN class=br0>(</SPAN>vt<SPAN class=br0>(</SPAN><SPAN class=nu0>7</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>7</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>9</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN> <SPAN class=nu0>2</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN>
    s<SPAN class=br0>(</SPAN>vt<SPAN class=br0>(</SPAN><SPAN class=nu0>7</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>8</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>9</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN> <SPAN class=nu0>8</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN>
    s<SPAN class=br0>(</SPAN>vt<SPAN class=br0>(</SPAN><SPAN class=nu0>8</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>4</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>8</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN> <SPAN class=nu0>4</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN>
    s<SPAN class=br0>(</SPAN>vt<SPAN class=br0>(</SPAN><SPAN class=nu0>8</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>5</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>8</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN> <SPAN class=nu0>1</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN>
    s<SPAN class=br0>(</SPAN>vt<SPAN class=br0>(</SPAN><SPAN class=nu0>8</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>6</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>8</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN> <SPAN class=nu0>9</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN>
    s<SPAN class=br0>(</SPAN>vt<SPAN class=br0>(</SPAN><SPAN class=nu0>8</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>9</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>9</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN> <SPAN class=nu0>5</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN>
    s<SPAN class=br0>(</SPAN>vt<SPAN class=br0>(</SPAN><SPAN class=nu0>9</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>5</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>8</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN> <SPAN class=nu0>8</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN>
    s<SPAN class=br0>(</SPAN>vt<SPAN class=br0>(</SPAN><SPAN class=nu0>9</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>8</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>9</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN> <SPAN class=nu0>7</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN>
    s<SPAN class=br0>(</SPAN>vt<SPAN class=br0>(</SPAN><SPAN class=nu0>9</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>9</SPAN><SPAN class=sy0>,</SPAN><SPAN class=nu0>9</SPAN><SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN> <SPAN class=nu0>9</SPAN><SPAN class=br0>)</SPAN><SPAN class=br0>]</SPAN>.
 
 
<SPAN class=sy0>%</SPAN> query solution
test<SPAN class=br0>(</SPAN>S<SPAN class=br0>)</SPAN> <SPAN class=sy0>:-</SPAN>
    test_board<SPAN class=br0>(</SPAN>B<SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN>
    colors<SPAN class=br0>(</SPAN>C<SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN>
    hints<SPAN class=br0>(</SPAN>H<SPAN class=br0>)</SPAN><SPAN class=sy0>,</SPAN>
    sudoku_solve<SPAN class=br0>(</SPAN>B<SPAN class=sy0>,</SPAN> C<SPAN class=sy0>,</SPAN> H<SPAN class=sy0>,</SPAN> <SPAN class=br0>[</SPAN><SPAN class=br0>]</SPAN><SPAN class=sy0>,</SPAN> S<SPAN class=br0>)</SPAN>.
</PRE></DIV></DIV>
<H2><SPAN class=editsection>[<A 
title="Edit section: Exceptionally difficult Sudokus (Hardest Sudokus)" 
href="http://en.wikipedia.org/w/index.php?title=Algorithmics_of_sudoku&amp;action=edit&amp;section=14">edit</A>]</SPAN> 
<SPAN class=mw-headline 
id=Exceptionally_difficult_Sudokus_.28Hardest_Sudokus.29>Exceptionally difficult 
Sudokus (Hardest Sudokus)</SPAN></H2>
<P>Some of the sudoku puzzles can only be solved using logic that is too complex 
for human solvers. Most would describe them as <I>unsolvable</I> after 
exhausting their arsenal of sudoku solving techniques and would proceed to a 
<I><A title="Trial and error" 
href="http://en.wikipedia.org/wiki/Trial_and_error">trial and error</A></I> path 
to reach a solution.</P>
<P>It was no surprise that computer programmers were interested in this subject, 
trying to generate even more difficult puzzles or even trying to find new ways 
to logically solve and rate them.</P>
<P>Rating puzzles that are beyond human capabilities proved to be difficult as 
different points of view regarding what could be considered a <I><A 
title=Yardstick href="http://en.wikipedia.org/wiki/Yardstick">yardstick</A></I> 
for measuring difficulty resulted in heterogeneous opinions on which puzzle is 
the <I>hardest of them all</I>.</P>
<P>Several active discussions on this issue took place on a number of popular 
sudoku forums since 2005.<SUP class=reference id=cite_ref-8><A 
href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#cite_note-8"><SPAN>[</SPAN>9<SPAN>]</SPAN></A></SUP><SUP 
class=reference id=cite_ref-9><A 
href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#cite_note-9"><SPAN>[</SPAN>10<SPAN>]</SPAN></A></SUP><SUP 
class=reference id=cite_ref-10><A 
href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#cite_note-10"><SPAN>[</SPAN>11<SPAN>]</SPAN></A></SUP> 
Several openly accessible solver programs became popular between users for the 
purpose of rating and generating such puzzles. <A title="Algorithmics of sudoku" 
href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#External_links"><I>(See: 
External links)</I></A></P>
<P>The following is a compilation of the latest hardest sudoku puzzles according 
to a number of openly accessible solver Programs:</P><PRE>Rating Program: gsf's sudoku q1 (rating) 
Rating: 99408 
Poster: JPF 
Label: Easter Monster 
1.......2.9.4...5...6...7...5.9.3.......7.......85..4.7.....6...3...9.8...2.....1 
1 . . | . . . | . . 2  
. 9 . | 4 . . | . 5 .  
. . 6 | . . . | 7 . .  
------+-------+------ 
. 5 . | 9 . 3 | . . .  
. . . | . 7 . | . . .  
. . . | 8 5 . | . 4 .  
------+-------+------ 
7 . . | . . . | 6 . .  
. 3 . | . . 9 | . 8 .  
. . 2 | . . . | . . 1  
</PRE><PRE>Rating Program: gsf's sudoku q1 (Processing time) 
Rating: 4m19s@2 GHz 
Poster: tarek 
Label: tarek071223170000-052 
..1..4.......6.3.5...9.....8.....7.3.......285...7.6..3...8...6..92......4...1... 
. . 1 | . . 4 | . . .  
. . . | . 6 . | 3 . 5  
. . . | 9 . . | . . .  
------+-------+------ 
8 . . | . . . | 7 . 3  
. . . | . . . | . 2 8  
5 . . | . 7 . | 6 . .  
------+-------+------ 
3 . . | . 8 . | . . 6  
. . 9 | 2 . . | . . .  
. 4 . | . . 1 | . . .  
</PRE><PRE>Rating Program: 1024 bIT Sudoku Solver (Processing time) 
Rating: 2840 milliseconds@2 GHz 
Poster: embyro 
..1..4.......6.3.5...9.....8.....7.3.......285...7.6..3...8...6..92......4...1... 
. . 1 | . . 4 | . . .  
. . . | . 6 . | 3 . 5  
. . . | 9 . . | . . .  
------+-------+------ 
8 . . | . . . | 7 . 3  
. . . | . . . | . 2 8  
5 . . | . 7 . | 6 . .  
------+-------+------ 
3 . . | . 8 . | . . 6  
. . 9 | 2 . . | . . .  
. 4 . | . . 1 | . . .  
</PRE><PRE>Rating Program: Nicolas Juillerat's Sudoku explainer 1.2.1 
Rating: 11.9 
Poster: tarek 
Label: golden nugget 
.......39.....1..5..3.5.8....8.9...6.7...2...1..4.......9.8..5..2....6..4..7..... 
. . . | . . . | . 3 9  
. . . | . . 1 | . . 5  
. . 3 | . 5 . | 8 . .  
------+-------+------ 
. . 8 | . 9 . | . . 6  
. 7 . | . . 2 | . . .  
1 . . | 4 . . | . . .  
------+-------+------ 
. . 9 | . 8 . | . 5 .  
. 2 . | . . . | 6 . .  
4 . . | 7 . . | . . .  
</PRE><PRE>Rating Program: dukuso's suexrat9 
Rating: 4483 
Poster: coloin 
Label: col-02-08-071 
.2.4.37.........32........4.4.2...7.8...5.........1...5.....9...3.9....7..1..86.. 
. 2 . | 4 . 3 | 7 . .  
. . . | . . . | . 3 2  
. . . | . . . | . . 4  
------+-------+------ 
. 4 . | 2 . . | . 7 .  
8 . . | . 5 . | . . .  
. . . | . . 1 | . . .  
------+-------+------ 
5 . . | . . . | 9 . .  
. 3 . | 9 . . | . . 7  
. . 1 | . . 8 | 6 . .  
</PRE><PRE>Rating Program: dukuso's suexratt (10000 2 option) 
Rating: 2141 
Poster: tarek 
Label: golden nugget 
.......39.....1..5..3.5.8....8.9...6.7...2...1..4.......9.8..5..2....6..4..7..... 
. . . | . . . | . 3 9  
. . . | . . 1 | . . 5  
. . 3 | . 5 . | 8 . .  
------+-------+------ 
. . 8 | . 9 . | . . 6  
. 7 . | . . 2 | . . .  
1 . . | 4 . . | . . .  
------+-------+------ 
. . 9 | . 8 . | . 5 .  
. 2 . | . . . | 6 . .  
4 . . | 7 . . | . . .
</PRE>
<H2><SPAN class=editsection>[<A title="Edit section: References" 
href="http://en.wikipedia.org/w/index.php?title=Algorithmics_of_sudoku&amp;action=edit&amp;section=15">edit</A>]</SPAN> 
<SPAN class=mw-headline id=References>References</SPAN></H2>
<DIV class="references-small references-column-count references-column-count-2" 
style="moz-column-count: 2; column-count: 2">
<OL class=references>
  <LI id=cite_note-0><B><A 
  href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#cite_ref-0">^</A></B> 
  <A class="external text" href="http://www.flickr.com/photos/npcomplete/" 
  rel=nofollow>"flickr.com/photos/npcomplete/"</A> 
  <LI id=cite_note-1><B><A 
  href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#cite_ref-1">^</A></B> 
  <A class="external text" 
  href="http://www.flickr.com/photos/npcomplete/2384354604/" 
  rel=nofollow>"flickr.com/photos/npcomplete/2384354604/"</A> <I>(Star Burst Leo 
  sudoku)</I> 
  <LI id=cite_note-Lewis.2C_R_.282007.29_pp_387-401-2>^ <A 
  href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#cite_ref-Lewis.2C_R_.282007.29_pp_387-401_2-0"><SUP><I><B>a</B></I></SUP></A> 
  <A 
  href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#cite_ref-Lewis.2C_R_.282007.29_pp_387-401_2-1"><SUP><I><B>b</B></I></SUP></A> 
  Lewis, R (2007) <I>Metaheuristics Can Solve Sudoku Puzzles</I> Journal of 
  Heuristics, vol. 13 (4), pp 387-401. 
  <LI id=cite_note-Perez.2C_Meir_and_Marwala.2C_Tshilidzi_.282008.29-3><B><A 
  href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#cite_ref-Perez.2C_Meir_and_Marwala.2C_Tshilidzi_.282008.29_3-0">^</A></B> 
  Perez, Meir and Marwala, Tshilidzi (2008) <I>Stochastic Optimization 
  Approaches for Solving Sudoku</I> arXiv:0805.0697. 
  <LI id=cite_note-4><B><A 
  href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#cite_ref-4">^</A></B> 
  <A class="external text" href="http://4c.ucc.ie/~hsimonis/sudoku.pdf" 
  rel=nofollow>"Sudoku as a constraint problem"</A> 
  <LI id=cite_note-5><B><A 
  href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#cite_ref-5">^</A></B> 
  <A class="external text" href="http://jacop.osolpro.com/" 
  rel=nofollow>"JaCoP"</A> 
  <LI id=cite_note-6><B><A 
  href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#cite_ref-6">^</A></B> 
  <A class="external text" 
  href="http://www.flickr.com/photos/npcomplete/2599486458/" rel=nofollow>"17 
  Clue Sudoku with Diagonal Symmetry"</A> 
  <LI id=cite_note-7><B><A 
  href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#cite_ref-7">^</A></B> 
  <A class="external text" 
  href="http://www.flickr.com/photos/npcomplete/2896377811/" rel=nofollow>"19 
  Clue Two-Way Symmetry"</A> 
  <LI id=cite_note-8><B><A 
  href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#cite_ref-8">^</A></B> 
  <A class="external text" 
  href="http://www.sudoku.com/boards/viewtopic.php?t=4212&amp;start=0" 
  rel=nofollow>"The hardest sudokus"</A> <I>On the Sudoku Players' Forums</I> 
  <LI id=cite_note-9><B><A 
  href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#cite_ref-9">^</A></B> 
  <A class="external text" 
  href="http://www.setbb.com/sudoku/viewtopic.php?t=103&amp;start=0&amp;mforum=sudoku" 
  rel=nofollow>"what is the hardest known suduko&nbsp;?"</A> <I>On the Sudoku 
  Programmers Forums</I> 
  <LI id=cite_note-10><B><A 
  href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#cite_ref-10">^</A></B> 
  <A class="external text" 
  href="http://www.sudoku.com/boards/viewtopic.php?t=5336&amp;start=0" 
  rel=nofollow>"How regular is to generate sudoku with difficulty 9+ SE?"</A> 
  <I>On the Sudoku Players' Forums</I> </LI></OL></DIV>
<H2><SPAN class=editsection>[<A title="Edit section: External links" 
href="http://en.wikipedia.org/w/index.php?title=Algorithmics_of_sudoku&amp;action=edit&amp;section=16">edit</A>]</SPAN> 
<SPAN class=mw-headline id=External_links>External links</SPAN></H2>
<UL>
  <LI><A class="external free" 
  href="http://diuf.unifr.ch/people/juillera/Sudoku/Sudoku.html" 
  rel=nofollow>http://diuf.unifr.ch/people/juillera/Sudoku/Sudoku.html</A> 
  <I>Sudoku Explainer by Nicolas Juillerat</I> (Popular for rating sudokus in 
  general) 
  <LI><A class="external free" 
  href="http://www.research.att.com/~gsf/man/man1/sudoku.html" 
  rel=nofollow>http://www.research.att.com/~gsf/man/man1/sudoku.html</A> 
  <I>sudoku by gsf</I> (Popular for rating the hardest sudokus amongst other 
  things) 
  <LI><A class="external free" href="http://magictour.free.fr/sudoku.htm" 
  rel=nofollow>http://magictour.free.fr/sudoku.htm</A><I>suexrat9 by dukuso</I> 
  (Popular for rating the hardest sudokus) 
  <LI><A class="external free" href="http://magictour.free.fr/suexratt.exe" 
  rel=nofollow>http://magictour.free.fr/suexratt.exe</A> <I>suexratt by 
  dukuso</I> (Popular for rating the hardest sudokus) 
  <LI><A class="external free" 
  href="http://www.emanueleferonato.com/2008/12/09/sudoku-creatorsolver-with-php/" 
  rel=nofollow>http://www.emanueleferonato.com/2008/12/09/sudoku-creatorsolver-with-php/</A> 
  <I>Sudoku creator/solver using Php</I> 
  <LI><A class="external free" 
  href="http://www.idontplaydarts.com/code/sudoku-solver/" 
  rel=nofollow>http://www.idontplaydarts.com/code/sudoku-solver/</A> <I>An open 
  source PHP Sudoku solver class using a Depth first Search</I> 
  <LI><A class="external text" 
  href="http://www.ams.org/notices/200904/rtx090400460p.pdf" rel=nofollow>A 
  Pencil-and-Paper Algorithm for Solving Sudoku Puzzles</A> quoted also in a 
  popular British newspaper the <A class="external text" 
  href="http://www.dailymail.co.uk/news/article-1163925/Puzzling-behaviour-Maths-professor-finds-formula-solve-ANY-Sudoku.html" 
  rel=nofollow>Daily Mail</A> 
  <LI><A class="external text" 
  href="http://home.comcast.net/~raagnew/site/?/page/Downloads" 
  rel=nofollow>Downloadable Excel Sudoku Assistant and Solver</A> 
  <LI><A class="external text" 
  href="http://www.microshell.com/database/postgresql/solving-sudoku-using-postgresql-plpgsql/" 
  rel=nofollow>Solving sudoku in PL/pgSQL</A> from Microshell. </LI></UL><!-- 
NewPP limit report
Preprocessor node count: 1010/1000000
Post-expand include size: 7880/2048000 bytes
Template argument size: 2370/2048000 bytes
Expensive parser function count: 2/500
--><!-- Saved in parser cache with key enwiki:pcache:idhash:8444301-0!1!0!default!!en!2 and timestamp 20091114040625 -->
<DIV class=printfooter>Retrieved from "<A 
href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku">http://en.wikipedia.org/wiki/Algorithmics_of_sudoku</A>"</DIV>
<DIV class=catlinks id=catlinks>
<DIV id=mw-normal-catlinks><A title=Special:Categories 
href="http://en.wikipedia.org/wiki/Special:Categories">Categories</A>: <SPAN 
dir=ltr><A title=Category:Sudoku 
href="http://en.wikipedia.org/wiki/Category:Sudoku">Sudoku</A></SPAN></DIV>
<DIV class=mw-hidden-cats-hidden id=mw-hidden-catlinks>Hidden categories: <SPAN 
dir=ltr><A title="Category:Articles needing cleanup from April 2007" 
href="http://en.wikipedia.org/wiki/Category:Articles_needing_cleanup_from_April_2007">Articles 
needing cleanup from April 2007</A></SPAN> | <SPAN dir=ltr><A 
title="Category:All pages needing cleanup" 
href="http://en.wikipedia.org/wiki/Category:All_pages_needing_cleanup">All pages 
needing cleanup</A></SPAN> | <SPAN dir=ltr><A 
title="Category:Articles that may contain original research from September 2007" 
href="http://en.wikipedia.org/wiki/Category:Articles_that_may_contain_original_research_from_September_2007">Articles 
that may contain original research from September 2007</A></SPAN> | <SPAN 
dir=ltr><A title="Category:All articles that may contain original research" 
href="http://en.wikipedia.org/wiki/Category:All_articles_that_may_contain_original_research">All 
articles that may contain original research</A></SPAN></DIV></DIV><!-- end content -->
<DIV class=visualClear></DIV></DIV></DIV></DIV>
<DIV id=column-one>
<DIV class=portlet id=p-cactions>
<H5>Views</H5>
<DIV class=pBody>
<UL lang=en xml:lang="en">
  <LI class=selected id=ca-nstab-main><A title="View the content page [c]" 
  accessKey=c 
  href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku">Article</A> 
  <LI id=ca-talk><A title="Discussion about the content page [t]" accessKey=t 
  href="http://en.wikipedia.org/wiki/Talk:Algorithmics_of_sudoku">Discussion</A> 

  <LI id=ca-edit><A 
  title="You can edit this page. &#10;Please use the preview button before saving. [e]" 
  accessKey=e 
  href="http://en.wikipedia.org/w/index.php?title=Algorithmics_of_sudoku&amp;action=edit">Edit 
  this page</A> 
  <LI id=ca-history><A title="Past versions of this page [h]" accessKey=h 
  href="http://en.wikipedia.org/w/index.php?title=Algorithmics_of_sudoku&amp;action=history">History</A> 
  </LI></UL></DIV></DIV>
<DIV class=portlet id=p-personal>
<H5>Personal tools</H5>
<DIV class=pBody>
<UL lang=en xml:lang="en">
  <LI id=pt-optin-try><A class=no-text-transform title="Try out new features" 
  href="http://en.wikipedia.org/w/index.php?title=Special:UsabilityInitiativeOptIn&amp;from=Algorithmics_of_sudoku">Try 
  Beta</A> 
  <LI id=pt-login><A 
  title="You are encouraged to log in; however, it is not mandatory. [o]" 
  accessKey=o 
  href="http://en.wikipedia.org/w/index.php?title=Special:UserLogin&amp;returnto=Algorithmics_of_sudoku">Log 
  in / create account</A> </LI></UL></DIV></DIV>
<DIV class=portlet id=p-logo><A title="Visit the main page" 
style="BACKGROUND-IMAGE: url(http://upload.wikimedia.org/wikipedia/en/b/bc/Wiki.png)" 
href="http://en.wikipedia.org/wiki/Main_Page"></A></DIV>
<SCRIPT type=text/javascript> if (window.isMSIE55) fixalpha(); </SCRIPT>

<DIV class="generated-sidebar portlet" id=p-navigation>
<H5 lang=en xml:lang="en">Navigation</H5>
<DIV class=pBody>
<UL>
  <LI id=n-mainpage-description><A title="Visit the main page [z]" accessKey=z 
  href="http://en.wikipedia.org/wiki/Main_Page">Main page</A> 
  <LI id=n-contents><A title="Guides to browsing Wikipedia" 
  href="http://en.wikipedia.org/wiki/Portal:Contents">Contents</A> 
  <LI id=n-featuredcontent><A title="Featured content — the best of Wikipedia" 
  href="http://en.wikipedia.org/wiki/Portal:Featured_content">Featured 
  content</A> 
  <LI id=n-currentevents><A 
  title="Find background information on current events" 
  href="http://en.wikipedia.org/wiki/Portal:Current_events">Current events</A> 
  <LI id=n-randompage><A title="Load a random article [x]" accessKey=x 
  href="http://en.wikipedia.org/wiki/Special:Random">Random article</A> 
</LI></UL></DIV></DIV>
<DIV class=portlet id=p-search>
<H5 lang=en xml:lang="en"><LABEL for=searchInput>Search</LABEL></H5>
<DIV class=pBody id=searchBody>
<FORM id=searchform action=/w/index.php><INPUT type=hidden value=Special:Search 
name=title> <INPUT id=searchInput title="Search Wikipedia" accessKey=f 
name=search> <INPUT class=searchButton id=searchGoButton title="Go to a page with this exact name if one exists" type=submit value=Go name=go>&nbsp; 
<INPUT class=searchButton id=mw-searchButton title="Search Wikipedia for this text" type=submit value=Search name=fulltext> 
</FORM></DIV></DIV>
<DIV class="generated-sidebar portlet" id=p-interaction>
<H5 lang=en xml:lang="en">Interaction</H5>
<DIV class=pBody>
<UL>
  <LI id=n-aboutsite><A title="Find out about Wikipedia" 
  href="http://en.wikipedia.org/wiki/Wikipedia:About">About Wikipedia</A> 
  <LI id=n-portal><A 
  title="About the project, what you can do, where to find things" 
  href="http://en.wikipedia.org/wiki/Wikipedia:Community_portal">Community 
  portal</A> 
  <LI id=n-recentchanges><A title="The list of recent changes in the wiki [r]" 
  accessKey=r href="http://en.wikipedia.org/wiki/Special:RecentChanges">Recent 
  changes</A> 
  <LI id=n-contact><A title="How to contact Wikipedia" 
  href="http://en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</A> 

  <LI id=n-sitesupport><A title="Support us" 
  href="http://wikimediafoundation.org/wiki/Support_Wikipedia/en">Donate to 
  Wikipedia</A> 
  <LI id=n-help><A title="Guidance on how to use and edit Wikipedia" 
  href="http://en.wikipedia.org/wiki/Help:Contents">Help</A> 
</LI></UL></DIV></DIV>
<DIV class=portlet id=p-tb>
<H5 lang=en xml:lang="en">Toolbox</H5>
<DIV class=pBody>
<UL>
  <LI id=t-whatlinkshere><A 
  title="List of all English Wikipedia pages containing links to this page [j]" 
  accessKey=j 
  href="http://en.wikipedia.org/wiki/Special:WhatLinksHere/Algorithmics_of_sudoku">What 
  links here</A> 
  <LI id=t-recentchangeslinked><A 
  title="Recent changes in pages linked from this page [k]" accessKey=k 
  href="http://en.wikipedia.org/wiki/Special:RecentChangesLinked/Algorithmics_of_sudoku">Related 
  changes</A> 
  <LI id=t-upload><A title="Upload files [u]" accessKey=u 
  href="http://en.wikipedia.org/wiki/Wikipedia:Upload">Upload file</A> 
  <LI id=t-specialpages><A title="List of all special pages [q]" accessKey=q 
  href="http://en.wikipedia.org/wiki/Special:SpecialPages">Special pages</A> 
  <LI id=t-print><A title="Printable version of this page [p]" accessKey=p 
  href="http://en.wikipedia.org/w/index.php?title=Algorithmics_of_sudoku&amp;printable=yes" 
  rel=alternate>Printable version</A> 
  <LI id=t-permalink><A title="Permanent link to this revision of the page" 
  href="http://en.wikipedia.org/w/index.php?title=Algorithmics_of_sudoku&amp;oldid=322090206">Permanent 
  link</A>
  <LI id=t-cite><A title="Information on how to cite this page" 
  href="http://en.wikipedia.org/w/index.php?title=Special:Cite&amp;page=Algorithmics_of_sudoku&amp;id=322090206">Cite 
  this page</A> </LI></UL></DIV></DIV></DIV><!-- end of the left (by default at least) column -->
<DIV class=visualClear></DIV>
<DIV id=footer>
<DIV id=f-poweredbyico><A href="http://www.mediawiki.org/"><IMG height=31 
alt="Powered by MediaWiki" 
src="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/poweredby_mediawiki_88x31.png" 
width=88></A></DIV>
<DIV id=f-copyrightico><A href="http://wikimediafoundation.org/"><IMG height=31 
alt="Wikimedia Foundation" 
src="Algorithmics of sudoku - Wikipedia, the free encyclopedia.files/wikimedia-button.png" 
width=88></A></DIV>
<UL id=f-list>
  <LI id=lastmod>This page was last modified on 26 October 2009 at 07:04. 
  <LI id=copyright>Text is available under the <A 
  href="http://en.wikipedia.org/wiki/Wikipedia:Text_of_Creative_Commons_Attribution-ShareAlike_3.0_Unported_License" 
  rel=license>Creative Commons Attribution-ShareAlike License</A><A 
  style="DISPLAY: none" href="http://creativecommons.org/licenses/by-sa/3.0/" 
  rel=license></A>; additional terms may apply. See <A 
  href="http://wikimediafoundation.org/wiki/Terms_of_Use">Terms of Use</A> for 
  details.<BR>Wikipedia® is a registered trademark of the <A 
  href="http://www.wikimediafoundation.org/">Wikimedia Foundation, Inc.</A>, a 
  non-profit organization.
  <LI><A class=internal 
  href="http://en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact us</A> 
  <LI id=privacy><A title="wikimedia:Privacy policy" 
  href="http://wikimediafoundation.org/wiki/Privacy_policy">Privacy policy</A> 
  <LI id=about><A title=Wikipedia:About 
  href="http://en.wikipedia.org/wiki/Wikipedia:About">About Wikipedia</A> 
  <LI id=disclaimer><A title="Wikipedia:General disclaimer" 
  href="http://en.wikipedia.org/wiki/Wikipedia:General_disclaimer">Disclaimers</A> 
  </LI></UL></DIV></DIV>
<SCRIPT type=text/javascript>if (window.runOnloadHook) runOnloadHook();</SCRIPT>
<!-- Served by srv246 in 0.037 secs. --></BODY></HTML>
